text:
# Appendix to a paper of Maisner and Nart

(Date: 31 October 2001)

## Abstract.

We prove that there is no genus-$`2`$ curve over $`𝐅_q`$ whose Jacobian has characteristic polynomial of Frobenius equal to $`x^4+(12q)x^2+q^2`$.

###### Key words and phrases:

Curve, abelian surface, zeta function

For every prime power $`q`$ let $`f_q`$ denote the polynomial $`x^4+(12q)x^2+q^2`$. In , Maisner and Nart observe that for all prime powers $`q64`$, no genus-$`2`$ curve over $`𝐅_q`$ has characteristic polynomial $`f_q`$. (By the characteristic polynomial of a curve we mean the characteristic polynomial of the Frobenius endomorphism of the Jacobian of the curve.) The purpose of this appendix is to prove that Maisner and Nart’s observation holds for all prime powers $`q`$.

###### Theorem.

There is no curve of genus $`2`$ over any finite field $`𝐅_q`$ whose characteristic polynomial is equal to $`f_q`$.

###### Proof.

Suppose, to obtain a contradiction, that $`C`$ is a genus-$`2`$ curve over a finite field $`𝐅_q`$ whose characteristic polynomial is equal to $`f_q`$. Note that then $`\mathrm{\#}C(𝐅_q)=q+1`$ and $`\mathrm{\#}C(𝐅_{q^2})=(q1)(q3)`$.

Let $`J`$ be the Jacobian of $`C`$, let $`\lambda `$ be the canonical principal polarization of $`J`$, let $`F`$ be the Frobenius endomorphism of $`J`$, and let $`V=q/F`$ be the Verschiebung endomorphism of $`J`$. Since $`f_q`$ is irreducible and its middle coefficient is coprime to $`q`$, we see that $`J`$ is a simple ordinary abelian surface, and it follows that $`K=(\mathrm{End}J)𝐐`$ is equal to the field $`𝐐(F)`$. In fact, $`K`$ is a totally imaginary quadratic extension of a totally real quadratic field $`K^+`$, and general theory (see \[3, p. 201\]) shows that the Rosati involution $`xx^{}`$ on $`K`$ is complex conjugation.

Let $`i`$ be the endomorphism $`FV`$ of $`J`$. It is easy to check that $`i^2=1`$, and it follows that $`i^{}i=1`$. Thus $`i`$ is an automorphism of $`J`$ that respects the polarization $`\lambda `$, so $`i`$ can be viewed as an automorphism of the polarized abelian variety $`(J,\lambda )`$. Since $`C`$ is hyperelliptic, Torelli’s theorem (see \[2, p. 202\]) shows that the natural map from the automorphism group of $`C`$ to the automorphism group of $`(J,\lambda )`$ is an isomorphism that takes the hyperelliptic involution to $`1`$. Thus, the automorphism $`i`$ of $`(J,\lambda )`$ gives us an automorphism $`\alpha `$ of $`C`$, defined over $`𝐅_q`$, whose square is the hyperelliptic involution.

Let $`W`$ denote the set of Weierstrass points of $`C`$, viewed as a set with an action of the absolute Galois group of $`𝐅_q`$. If $`P`$ is a geometric point of $`C`$ whose orbit under the action of $`\alpha `$ contains fewer than four points, then $`P`$ must be fixed by $`\alpha ^2=1`$, so $`P`$ must lie in $`W`$. Thus, for every finite extension field $`k`$ of $`𝐅_q`$ we have $`\mathrm{\#}C(k)\mathrm{\#}W(k)mod4.`$

Suppose that $`q`$ is odd. Then $`W`$ consists of six points, and we will show that exactly two of these points are fixed by $`\alpha `$.

Consider the map $`C𝐏^1`$ obtained from the hyperelliptic involution, and let $`W^{}`$ denote the set of six points of $`𝐏^1`$ lying under the Weierstrass points of $`C`$. The automorphism $`\alpha `$ induces an involution $`\beta `$ of $`𝐏^1`$ that takes the set $`W^{}`$ to itself. Geometrically, this involution is conjugate to the involution $`xx`$, so if none of the points in $`W^{}`$ were fixed by $`\beta `$ the curve $`C`$ would be isomorphic (over the algebraic closure of $`𝐅_q`$) to a curve of the form $`y^2=f(x^2)`$, where $`f`$ is a cubic polynomial. But then $`\alpha `$ would have to be of the form $`(x,y)(x,\pm y)`$, and such an automorphism has order two. Thus, $`\beta `$ must fix at least one of the six points of $`W^{}`$. But the points not fixed by $`\beta `$ come in plus/minus pairs, so there must be at least two points of $`W^{}`$ fixed by $`\beta `$. Since $`xx`$ has exactly two fixed points in $`𝐏^1`$, there must be exactly two points of $`W^{}`$ fixed by $`\beta `$. It follows that exactly two points of $`W`$ are fixed by $`\alpha `$, as claimed.

Since $`\alpha `$ is defined over $`𝐅_q`$, the two points of $`W`$ fixed by $`\alpha `$ must be defined over $`𝐅_{q^2}`$. Thus, $`\mathrm{\#}W(𝐅_{q^2})2`$. But we also have

$$\mathrm{\#}W(𝐅_{q^2})\mathrm{\#}C(𝐅_{q^2})=(q1)(q3)0mod4,$$

so we must have $`\mathrm{\#}W(𝐅_{q^2})=4`$. But this is impossible, as one can see by asking where the other two points of $`W`$ are defined. This proves the theorem for odd $`q`$.

Suppose that $`q`$ is a power of $`2`$. Then $`q`$ must be a multiple of $`4`$, because if $`q`$ were $`2`$ the curve $`C`$ would have $`1`$ points over $`𝐅_4`$. We see that $`\mathrm{\#}W(𝐅_q)1mod4`$ and $`\mathrm{\#}W(𝐅_{q^2})3mod4`$. But a genus-$`2`$ curve in characteristic $`2`$ has at most three Weierstrass points, so $`C`$ must have exactly three Weierstrass points, and exactly one of them is defined over $`𝐅_q`$.

Once again we let $`W^{}`$ denote the points of $`𝐏^1`$ lying under the Weierstrass points of $`C`$ and we let $`\beta `$ be the involution of $`𝐏^1`$ obtained from $`\alpha `$. Clearly $`\beta `$ must fix the unique point of $`W^{}(𝐅_q)`$. But $`\beta `$ cannot fix the other two points of $`W^{}`$, because in that case $`\beta `$ would be the identity on $`𝐏^1`$, and $`\alpha `$ could not have order four. Thus, $`\beta `$ must swap the other two points of $`W^{}`$. It follows that over the algebraic closure of $`𝐅_q`$ we can write $`C`$ as $`y^2+y=ax+b/x+b/(x+1)`$, where we have chosen the coordinates so that $`\beta `$ is given by $`xx+1`$. But then $`\alpha `$ must send $`(x,y)`$ to $`(x+1,y+c)`$ where $`c^2+c=a`$, and this automorphism has order two. Once again we obtain a contradiction, and the theorem is proved for even $`q`$ as well. ∎

Maisner and Nart also note that for every odd prime power $`q<64`$, no genus-$`2`$ curve over $`𝐅_q`$ has characteristic polynomial $`g_q=x^4+(22q)x^2+q^2`$. The obvious conjecture is that the same is true for all odd prime powers $`q`$. Unfortunately, the argument we used above cannot be easily modified to prove this conjecture; the critical fact we used was that the ring $`𝐙[F,V]`$ contains a root of unity other than $`\pm 1`$, and this is no longer true when we replace $`f_q`$ with $`g_q`$ in our argument.


format: text

text:
# Quarkonium Formation at High Energy

## 1 GENERIC EXPECTATIONS FOR LARGE $`N_{c\overline{c}}`$

At heavy ion collision energies at RHIC and LHC, the initial number of heavy quark pairs produced in each collision will be qualitatively different than the number produced at SPS energies. For example, the number of charm quark pairs is expected to be of the order of ten at RHIC and several hundred at LHC in the most central collisions . Let us attempt to extract features of $`J/\psi `$ formation from the initially-produced charm quarks which are independent of detailed dynamics. We consider scenarios in which the formation of $`J/\psi `$ is allowed to proceed through any combination of one of the $`N_c`$ charm quarks with one of the $`N_{\overline{c}}`$ anticharm quarks which result from the initial production of $`N_{c\overline{c}}`$ pairs in a central heavy ion collision. For a given charm quark, one expects then that the probability $`𝒫`$ to form a $`J/\psi `$ is just proportional to the number of available anticharm quarks relative to the number of light antiquarks,

$$𝒫N_{\overline{c}}/N_{\overline{u},\overline{d},\overline{s}}N_{c\overline{c}}/N_{ch},$$
(1)
where we normalize the number of light antiquarks by the number of produced charged hadrons. Since this ratio is generally very small, one can simply multiply by the number of available charm quarks $`N_c`$ to obtain the total number of $`J/\psi `$ expected in a given event.

$$N_{J/\psi }N_{c\overline{c}}^{}{}_{}{}^{2}/N_{ch},$$
(2)
where the use of the initial values $`N_{c\overline{c}}=N_c=N_{\overline{c}}`$ is again justified by the relatively small number of bound states formed. For an ensemble of events, the average number of $`J/\psi `$ per event is calculated from the average value of initial charm $`<N_{c\overline{c}}>`$, and we neglect fluctuations in $`N_{ch}`$.

$$<J/\psi >=\lambda (<N_{c\overline{c}}>+1)<N_{c\overline{c}}>/N_{ch},$$
(3)
where we place all dynamical dependence in the parameter $`\lambda `$. \[One can extend this formula to the case where $`J/\psi `$ formation is effective not over the entire rapidity range $`Y_{total}`$, but only if the quark and antiquark are within the same rapidity interval $`\mathrm{\Delta }y`$. In this case one makes the replacement $`<N_{c\overline{c}}>+1<N_{c\overline{c}}>+Y_{total}/\mathrm{\Delta }y`$.\]

The essential property of this result is that the growth with energy of the quadratic dependence on total charm  is expected to be much stronger than the corresponding growth of total particle production in heavy ion collisions . $`J/\psi `$ production without this quadratic mechanism is typically some small energy-independent fraction of total initial charm production , so that we can expect the quadratic formation to become dominant at high energy.

We show numerical results in Table 1 for these quantities with a prefactor $`\lambda `$ of unity. Estimates for the charm and particle numbers are very approximate, but serve to show the anticipated trend with energy. At SPS, this formation mechanism is most probably insignificant. At RHIC it is comparable with “normal” formation, while at LHC one might expect it to be dominant. Of course, the exact result will depend on the details of the physics which controls the formation.

## 2 STATISTICAL HADRONIZATION MODEL

This model is motivated by the success of attempts to explain the relative abundances of light hadrons produced in high energy interactions in terms of the predictions of a hadron gas in chemical and thermal equilibrium . Such fits, however, are not able to describe the abundances of hadrons containing charm quarks. This can be understood in terms of the long time scales required to approach chemical equilibrium for heavy quarks. However, it is expected that for high energy heavy ion collisions the initial production of charm quark pairs exceeds the number expected at chemical equilibrium as determined by the light hadron abundances. The statistical hadronization model  assumes that at hadronization these charm quarks are distributed into hadrons according to chemical equilibrium, but adjusted by a factor $`\gamma _c`$ which accounts for oversaturation of charm. One power of this factor multiplies a given thermal hadron population for each charm or anticharm quark contained in the hadron. Thus the relative abundance of $`J/\psi `$ to that of D mesons, for example, will be enhanced in this model. The enhancement factor is determined by conservation of charm, again using the time scale argument to justify neglecting pair production or annihilation before hadronization.

$$N_{c\overline{c}}=\frac{1}{2}\gamma _cN_{open}\frac{I_1(\gamma _cN_{open})}{I_0(\gamma _cN_{open})}+\gamma _{c}^{}{}_{}{}^{2}N_{hidden},$$
(4)
where $`N_{open}`$ and $`N_{hidden}`$ are calculated in the thermal equilibrium model grand canonical ensemble. The ratio of Bessel functions is an approximate correction factor  which converts to canonical ensemble particle numbers. This factor will only be significant for non-central collisions or lower energies in which the absolute number of charm pairs is quite small .

We show in Figure 2 calculated $`\gamma _c`$ values. At large total charm there is linear behavior, which leads to the quadratic growth of $`J/\psi `$ formation. It is interesting to note that the canonical suppression effect can be very well approximated by using a grand canonical formalism, supplemented by the averaging process for $`N_{c\overline{c}}^2`$ over a distribution of events.

Figure 2 shows several applications for RHIC conditions. The centrality dependence is modeled by the number of nucleon participants, and one sees the change in shape due to the transition between canonical and grand canonical formalism. The absolute magnitudes of $`<J/\psi >`$/charm are comparable with the initial production estimates of a fraction of a percent, indicating that this process may overwhelm suppression for central collisions at RHIC.

## 3 KINETIC FORMATION MODEL

In this model, we investigate the possibility to form $`J/\psi `$ directly in a deconfined medium. The formation will take advantage of the mobility of initially-produced charm quarks in a spatial region of deconfinement, such that all combinations of a charm plus anticharm are allowed to form a bound state. For the purposes of this study, we consider a physical picture of deconfinement in which quarkonium is suppressed via collisions with free gluons . The dominant formation process, in which a quark and an antiquark in a relative color octet state are captured into a color singlet bound quarkonium state and emit a color octet gluon, is simply the inverse of the breakup reaction. It is then an inevitable consequence of this picture of suppression that the corresponding formation process must also take place.

The time evolution if the $`J/\psi `$ population is given by the rate equation

$$\frac{dN_{J/\psi }}{d\tau }=\lambda _\mathrm{F}N_cN_{\overline{c}}[V(\tau )]^1\lambda _\mathrm{D}N_{J/\psi }\rho _g,$$
(5)
with $`\rho _g`$ the number density of gluons. The reactivity $`\lambda `$ is the reaction rate $`\sigma v_{\mathrm{rel}}`$ averaged over the momentum distribution of the initial participants, i.e. $`c`$ and $`\overline{c}`$ for $`\lambda _F`$ and $`J/\psi `$ and $`g`$ for $`\lambda _D`$. The gluon density is determined by the equilibrium value in the QGP at each temperature. The system undergoes a longitudinal isentropic expansion, which fixes the time-dependence of the volume V($`\tau `$). It is evident that the solution of Equation 5 grows quadratically with initial charm $`N_{c\overline{c}}`$, as long as the total $`J/\psi N_{c\overline{c}}`$.

$$N_{J/\psi }(\tau _f)=ϵ(\tau _f)\times [N_{J/\psi }(\tau _0)+N_{c\overline{c}}^2_{\tau _0}^{\tau _f}\lambda _\mathrm{F}[V(\tau )ϵ(\tau )]^1𝑑\tau ],$$
(6)
where $`\tau _f`$ is the hadronization time determined by the initial temperature ($`T_0`$ is a variable parameter) and final temperature ($`T_f`$ = 150 MeV ends the deconfining phase). The function $`ϵ(\tau _f)=e^{_{\tau _0}^{\tau _f}\lambda _\mathrm{D}\rho _g𝑑\tau }`$ would be the suppression factor in this scenario if the formation mechanism were neglected.

The momentum distribution of the charm quarks is allowed to vary over a wide range of possibilities. At one extreme we use a thermal equilibrium distribution at the QGP temperature. We also consider a distribution unchanged from that introduced in the initial perturbative QCD processes, plus several intermediate distributions with decreasing rapidity widths. The centrality dependence can also be modeled, using nuclear collision geometry to set the various spatial scales. For details, see Ref. .

We show the resulting ratios $`N_{J/\psi }`$/$`N_{c\overline{c}}`$ in Figure 4 (for RHIC) and Figure 4 (for LHC) for a full range of the initial charm quark rapidity distributions. Shown for comparison are some statistical hadronization model results, plus an indication of the value if only initial (vacuum) production were present. It is evident that although the absolute values depend strongly on the charm momentum distribution, the magnitudes are substantially above that expected if only initial production plus plasma suppression were present. The centrality dependence is quite striking. Even after normalizing to initial charm, the ratio rises with increasing centrality.

## 4 SUMMARY

Expectations based on general grounds for enhanced formation of heavy quarkonium in relativistic heavy ion collisions have been verified in two different models. In particular, one expects at RHIC and LHC to see an enhancement in the heavy quarkonium formation rate, even when compared to unsuppressed production via elementary nucleon-nucleon collisions in vacuum. The magnitude of this effect is expected to grow with the centrality of the heavy ion collision, just opposite to the predictions of various suppression scenarios. The physics bases for these models, however, are quite distinct. Their differences should manifest themselves in details of the magnitudes and centrality dependence. In this regard, it is essential to have a simultaneous measurement of open flavor production to serve as an unambiguous baseline.


text:
# Spin and density overlaps in the frustrated Ising lattice gas

## I Introduction

In the last years, a scenario has emerged for the theoretical description of structural glasses, in which the behavior of glasses is characterized by two different temperatures. The higher temperature $`T_c`$, identified with the critical temperature of the ideal mode-coupling theory, corresponds to a crossover in the dynamical behavior of the glass, characterized by a single relaxation time for $`T>T_c`$, and by a two-step relaxation for $`T<T_c`$. Below $`T_c`$, the free energy landscape in the phase space is splitted into an extensive number of valleys, separated by high barriers, and the dynamics is separated in a fast motion inside the valley, and a much slower motion among different valleys. The number of valleys accessible to the system at the temperature $`T`$, can be expressed by the formula $`𝒩=\mathrm{exp}(N\mathrm{\Sigma }(T))`$, where $`N`$ is the number of particles in the system, and $`\mathrm{\Sigma }(T)`$ is the so-called configurational entropy. The second temperature $`T_K`$, identified with the Kauzmann temperature and the critical temperature of the Adam and Gibbs theory, is characterized by the vanishing of the configurational entropy $`\mathrm{\Sigma }(T)`$, and the divergence of the relaxation time of the system with a Vogel-Fulcher-Tamman law.

This picture is corroborated by the analogy with a class of mean field models, the $`p`$-spin glasses. These models undergo a dynamical transition at a temperature $`T_d`$, where the phase space splits into an extensive number of metastable states, and the correlation functions show a singularity of the same type of the one predicted by mode-coupling theory. At a lower temperature $`T_s`$ the number of metastable states becomes non-extensive, that is the configurational entropy vanishes, and for $`T<T_s`$ the model shows a 1-step replica symmetry breaking. It has been longly debated to what extent this analogy, between structural glasses and $`p`$-spin models, can be pushed forward. In particular one may ask if structural glasses exhibit some kind of replica symmetry breaking, and if they are in the same universality class of $`p`$-spin models or not. There are presently some results that point in this direction. First principle computations of the equilibrium thermodynamics of simple fragile glasses seem to be consistent with this picture , and the off-equilibrium fluctuation-dissipation ratio, in molecular dynamics simulations of supercooled liquids , shows the same pattern observed in $`p`$-spin glasses and predicted for 1-step RSB models.

Nevertheless, there are still some important differences between structural glasses and $`p`$-spin models. In $`p`$-spin glasses the relevant variables are the spin orientations, and there is explicit quenched disorder in the Hamiltonian. On the other hand, in glasses the relevant variables are the particle positions, and there are no quenched interactions in the Hamiltonian, but the disorder is “self-generated” by the geometrical hindrance that the particles exert on each other. Furthermore, $`p`$-spin glasses are mean-field models, while structural glasses live in finite dimension. This means among other things that metastable states in $`p`$-spin models have infinite lifetime, and the dynamical transition $`T_d`$ corresponds to a divergence of the relaxation times, while in finite dimensional models the barriers between free energy valleys can be overcome by “hopping” processes, which restore ergodicity even below the crossover temperature $`T_c`$. Furthermore the $`p`$-spin model, if studied in three dimensions, loses many of its mean field “glassy” properties, and shows a transition similar to the full replica symmetry breaking transition of Ising spin glasses, though with some remarkable differences.

The frustrated Ising lattice gas was introduced some time ago as a simple finite dimensional lattice model of a glass-forming liquid, in order to overcome some of the limitations of $`p`$-spin models. Each lattice site carries two kinds of variables, a lattice gas variable $`n_i=0,1`$, which represent the presence or absence of a particle on the $`i`$-th site, and an Ising spin variable $`S_i`$, which represent an internal degree of freedom of the particle, such as for example the orientation of a non-symmetrical molecule. The Hamiltonian of the model is

$$=J\underset{ij}{}(1ϵ_{ij}S_iS_j)n_in_j\mu \underset{i}{}n_i,$$
(1)
where $`ϵ_{ij}=\pm 1`$ are quenched variables. In the limit $`J\mathrm{}`$, the first term of the Hamiltonian implies that two nearest neighbor sites can be simultaneously occupied by two particles only if their spin variables satisfy the constraint $`ϵ_{ij}S_iS_j=1`$. Therefore, if we identify the variables $`S_i`$ with the orientation of a non-symmetrical molecule, this condition means that two molecules can be near only if their relative orientation is appropriate.

Being constituted essentially by diffusing particles, this model is suited to study quantities like the diffusion coefficient, or the density autocorrelation functions, that are usually important in the study of liquids. Indeed, the model has proven to reproduce fairly well many features of supercooled glass-forming liquids, as for example the “cage effect”. At low temperature and high density, the model shows a two step relaxation in the self correlation function and in the mean square displacement. Furthermore, being a finite dimensional model, it is suitable to study activated processes, that are absent in mean field models.

Although the model has been extensively studied by Monte Carlo simulations  and in mean field , there are still many unsolved problems, concerning the type of transition presented by the model. In particular, it would be interesting to study if, in finite dimension, density and spin variables become critical at the same point, and what kind of replica symmetry breaking they show in the spin glass phase.

In this paper, we study the static and dynamical equilibrium properties of the model in the limit $`J\mathrm{}`$. We will evaluate the equilibrium overlap distribution of spin and density variables, the equilibrium autocorrelation functions of the self-overlaps, and the self-diffusion coefficient.

## II Spin and density overlap distributions

We have simulated the frustrated Ising lattice gas by means of the parallel tempering technique . With this technique one can thermalize the system at high chemical potential (high density), where the conventional Monte Carlo algorithms suffer of extremely long autocorrelation times. One has to simulate several identical replicas of the system, at different chemical potentials $`\mu _0<\mathrm{}<\mu _n`$, where $`\mu _0`$ corresponds to a low density and very short autocorrelation time, and $`\mu _n`$ to the highest value of the chemical potential that one wants to investigate. Each step of the algorithm consists of the following two substeps: for each replica, perform a conventional Monte Carlo step with the given temperature and chemical potential; for each pair of replicas with adjacent chemical potentials, try to swap them with probability $`P_{\text{swap}}=\mathrm{min}(1,\mathrm{exp}(\beta \mathrm{\Delta }\mu \mathrm{\Delta }n))`$, where $`\mathrm{\Delta }n`$ is the difference in the number of particles of the two replicas considered, and $`\mathrm{\Delta }\mu `$ the difference of their chemical potentials. If one chooses carefully the set of chemical potentials, then the replicas will perform a random walk over the interval $`[\mu _0,\mu _n]`$. The time needed to go from $`\mu _0`$ to $`\mu _n`$ and back again is called ergodic time, and can be considered as the maximum autocorrelation time of the system.

We have simulated the model for $`J=\mathrm{}`$ and $`\beta =1`$, between the chemical potentials $`\mu _{\text{min}}=1.69`$ and $`\mu _{\text{max}}=10.69`$, for system sizes $`6^3`$, $`8^3`$ and $`10^3`$. In the first case we have performed the simulation over 12 values of the chemical potential, in the second over 16 values, and in the third over 25 values. The exact values of the chemical potentials were determined by an algorithm which tried to optimize the intervals, in order to obtain the same swap rate between all the adjacent replicas. For each value of the chemical potential we simulated two replicas, in order to evaluate spin and density overlap. The thermalization of the systems was checked by looking at the densities of the replicas, and waiting until they did not show any sensible drift in time. The thermalization time was greater than $`10^6`$ steps.

After having thermalized the systems, at each parallel tempering step we collected, for each pair of replicas at the same chemical potential, the spin overlap $`q_s=\frac{1}{N}_iS_i^\alpha n_i^\alpha S_i^\beta n_i^\beta `$ and the density overlap $`q_d=\frac{1}{N}_in_i^\alpha n_i^\beta `$, where the superscripts $`\alpha `$ and $`\beta `$ refer to the two replicas, and $`N`$ is the number of spins. We simulated the systems for up to $`10^7`$ steps for the largest size, and checked the symmetry of the spin overlap distribution to be sure that the simulation time was sufficient. All the relevant quantities were averaged over 32 disorder realizations, and errors were evaluated from the fluctuations between different realizations.

In Fig. 1 the equilibrium distribution of the spin overlap is shown, for the largest size $`10^3`$ and for different chemical potentials. For high chemical potential, the distribution develops two peaks, separated by a continuous plateau. This is typical of models with a continuous replica symmetry breaking, like the Ising spin glass in three dimensions. Note that, for the highest chemical potential, the distribution between the two peaks is not a constant plateau, but is formed by many small peaks. This can be due to the fact that, at high chemical potential or low temperature, averaging over more than 32 disorder realizations is needed to obtain a constant plateau. The continuous replica symmetry breaking is associated with the divergence of the spin glass susceptibility, defined as $`\chi _{SG}=Nq_s^2`$, where $`\mathrm{}`$ denotes both the thermal average for a given set of interactions and the average over the disorder realizations. We have evaluated $`\chi _{SG}`$ for the different sizes and chemical potential, and the result is shown in Fig. 2. The behavior of the susceptibility confirms the presence of a thermodynamical second order transition. The exact value of the chemical potential at the transition can be evaluated by looking at the Binder parameter $`g=\frac{1}{2}(3q_s^4/q_s^2^2)`$, that is shown in Fig. 3. The curves corresponding to the different sizes cross at the chemical potential $`\mu _c=3.67`$. Once we have located the transition, we can try to evaluate the critical exponents, using the relation $`\chi _{SG}(L,\mu )=L^{2\eta }\stackrel{~}{\chi }_{SG}[L^{1/\nu }(\mu \mu _c)]`$, that should be valid around the transition, with $`\stackrel{~}{\chi }_{SG}[x]`$ a universal curve. In Fig. 4 the best fit is shown, obtained for the values $`\eta =0`$ and $`\nu =1`$. Note that these exponents were obtained also by Campellone et al.  in the three-dimensional version of the $`p`$-spin model. They are different from the exponents found in the Ising spin glass, $`\nu =1.7\pm 0.3`$ and $`\eta =0.35\pm 0.05`$ . This suggests that the transition could belong to a different universality class with respect to the Ising spin glass.

We have then evaluated the equilibrium distribution of the density overlap, which is shown in Fig. 5 for the largest size and for different chemical potentials. The non-linear compressibility $`\kappa _{nl}=N(q_d^2q_d^2)`$ is shown in Fig. 6 as a function of the chemical potential. The arrow in Fig. 6 marks the point where the spin variables undergo the transition, as signaled by the crossing of the Binder parameter, and the spin glass susceptibility diverges. It is evident that this point does not correspond to a divergence of the non-linear compressibility. Therefore the divergence of the spin glass susceptibility is due to the fluctuations of spin variables $`S_i`$, and not to the fluctuations of the density variables $`n_i`$. We have also evaluated the Binder parameter of the density overlap (not shown), which shows a non-monotonic behavior, becoming negative for low density and positive at high density, similarly to what is observed in the finite-dimensional p-spin . Indeed the curves for different sizes do not cross at a definite point, so they cannot be used to localize the transition (if any) of the density variables.

It remains to be determined whether or not the density variables exhibit a transition not manifested by a divergence of the non-linear compressibility. Note that for very high chemical potential the equilibrium distribution of the density overlap develops a secondary minimum. This could correspond to a transition of different kind, perhaps similar to the 1-step replica symmetry breaking transition of the $`p`$-spin models.

## III Relaxation functions of spin and density self-overlap

The frustrated Ising lattice gas is known to have very large relaxation times at high density or low temperature . Here we want to evaluate the relaxation times of the spin self-overlap, defined as $`q_s(t)=\frac{1}{N}_iS_i(t^{})n_i(t^{})S_i(t^{}+t)n_i(t^{}+t)`$, and the density self-overlap $`q_d(t)=\frac{1}{N}_i(n_i(t^{})n_i(t^{}+t)n_i(t^{})^2)`$, where the average $`\mathrm{}`$ is done over the reference time $`t^{}`$. We have simulated the model for system size $`20^3`$, and 10 chemical potentials between $`\mu =2.583`$ and 3.661, in the following manner. We start with an empty system, with the interactions randomly chosen, thermalize at the given chemical potential for a given time $`\mathrm{\Delta }t`$, save the obtained configuration, and then simulate the model saving the self-overlaps $`q_s(t)`$ and $`q_d(t)`$ with respect to the configuration at the end of thermalization. Then we repeat the process again with a different disorder configuration and thermal noise. The thermalization time $`\mathrm{\Delta }t`$ is at least 10 times larger than the time needed to the self-overlap to decay to the value 0.1, except for the three highest chemical potentials, for which the thermalization time was shorter. The self-overlaps were averaged over at least 100 different runs, and errors were evaluated from the fluctuations between different runs. When evaluating the density self-overlap $`q_d(t)`$, the quantity $`\frac{1}{N}_in_i(t^{})^2`$ can be taken equal to the average density overlap $`q_d`$ at equilibrium, as calculated in the parallel tempering simulations.

In Fig. 7 the relaxation functions of the spin self-overlap are shown. The solid lines are fit with the function $`ct^x\mathrm{exp}((t/\tau )^\beta )`$, proposed by Ogielski for the Ising spin glass . The exponent $`\beta `$ is nearly constant within the errors for all the chemical potentials considered, and slightly greater than 0.5, while the exponent $`x`$ varies between 0.2 for the lowest chemical potential to 0.1 for the highest. The correlation times $`\tau `$ are shown in Fig. 8, excluding the last three points, which are likely to suffer from insufficient thermalization or finite size effects. A power law fit $`\tau |\mu \mu _c|^{z\nu }`$ gives a dynamical exponent $`z=7.4`$, slightly greater than the exponent $`z=6.0\pm 0.8`$ found by Ogielski for the Ising spin glass.

In Fig. 9 the relaxation functions of the density self-overlap are shown, for the same system size and chemical potentials. Note that the relaxation times grow very slowly with respect to those of the spin self-overlap. This supports the conclusion that the transition at $`\mu _c=3.67`$ does not involve the density variables $`n_i`$. The latter probably undergo a transition at a higher chemical potential, inside the phase where the spin variables are frozen.

## IV Diffusivity

We have simulated the model with a purely diffusive dynamics, in the following way. We start with an empty lattice, with random interactions, and then slowly raise the chemical potential, until a given density is reached. Then we switch to a purely diffusive dynamics, with conserved number of particles, and thermalize the system at the given density. After having thermalized the system, we collect the mean square displacement $`r^2(t)`$ of the particles as a function of time. The long time regime of the mean square displacement is of the form $`r^2(t)=Dt`$, from which we extract the diffusion coefficient $`D`$. To each density, we associate a chemical potential from the equilibrium relation between the two quantities.

In Fig. 10 the diffusion coefficient $`D`$ is shown for a system size $`16^3`$ as a function of the chemical potential. For high chemical potential, it can be well fitted by an Arrhenius form, $`D=ae^{\alpha \mu }`$. Therefore, the diffusion of the particles seems to stop only at $`\mu \mathrm{}`$, which corresponds to $`T0`$. The arrow marks the point where the spin variables undergo the spin glass-like transition: apparently no anomaly in the diffusivity shows up in correspondence of the transition. In the inset, the diffusivity as a function of the density is shown. Note that for $`\mu \mathrm{}`$ the density goes to a maximum value $`\rho _{\text{max}}0.68`$. The diffusivity can be well fitted by a power law $`D=a(\rho _0\rho )^\gamma `$, where $`\rho _0=0.681`$ and $`\gamma =1.38`$.

## V Conclusions

We have studied the static and dynamical properties of the frustrated Ising lattice gas at equilibrium. A spin glass-like transition is found in the spin variables, signaled by the crossing of the Binder parameter, the divergence of the non-linear susceptibility, and the development of a continuous replica symmetry breaking in the spin overlap distribution. The equilibrium autocorrelation functions of the spin overlap can be well fitted by an Ogielsky form, with a correlation time diverging at the critical point. On the other hand, the density variables seem to be affected little by the transition, showing no divergence either in the non-linear compressibility, or in the autocorrelation time.

The freezing of the model at the chemical potential $`\mu _c`$ is therefore connected with a second order transition in the spin variables, more similar to the freezing of the Ising spin glass than to the mode-coupling transition of structural glasses. One cannot exclude that the density variables undergo a $`p`$-spin-like transition at a higher density, characterized by a 1-step replica symmetry breaking and a discontinuity of the Edwards-Anderson parameter defined in terms of density variables. This fact is suggested by the development of a secondary peak in the density overlap distribution at very high chemical potential, as well as by the measurements of the off-equilibrium fluctuation-dissipation ratio , but more work is needed to clarify this point.

## Acknowledgments

This work was partially supported by the European TMR Network-Fractals (Contract No. FMRXCT980183), MURST-PRIN-2000 and INFMPRA(HOP). We acknowledge the allocation of computer resources from INFM Progetto Calcolo Parallelo.


text:
# Constructing Fresnel reflection coefficients by ruler and compass

## I Introduction

The reflection of a plane wave at a planar interface between two homogeneous and isotropic media is a well-known phenomenon. From a general perspective, that embraces all kinds of waves, the physics of reflection is well understood: mismatched impedances generate the reflected and transmitted waves, while the application of the proper boundary conditions at the discontinuity provides the corresponding amplitude coefficients CR68 .

For light waves the impedance is proportional to the refractive index. Therefore, the mismatching of impedances gives Snell’s law, which, in fact, is independent of the precise form of boundary conditions. On the other hand, the continuity across the boundary of the tangential components of the electric and magnetic fields yields the reflection and transmission amplitudes, which constitute the famous Fresnel formulas BO99 ; HE99 ; PE87 .

In view of their simplicity and elegance, it seems difficult to say anything new about Fresnel formulas. However, a quick look at the index of, e.g., this journal HE73 ; OL79 ; PA83 ; DO85 ; BE87 ; ZI88 ; NA89 ; LO91 ; DO92 ; RE92 ; MI96 ; OU01 , immediately reveals a steady flow of papers devoted to subtle aspects of this problem, which shows that the topic is far richer than one might naively expect.

Fresnel formulas provide complete optical information about the interface. Although it is possible to fully examine their physical implications by a purely algebraic analysis, the discussion is usually carried out by using plots of the coefficients in terms of the angle of incidence. This is mainly due to the belief that graphical results convey information more readily than algebraic formulas. In this spirit, it has also been proposed the use of geometrical methods LE22 ; KO75 ; DO80  to analyze the problem. In our opinion, these geometrical approaches are still worth exploring in order to take full advantage of them. Thus, in this paper we propose a new and extremely simple method that allows one to construct Fresnel formulas by ruler and compass. Geometrical construction by ruler and compass is a fascinating problem since ancient times, and offers the additional advantage for the students of easily visualizing the steps of any construction and how it varies for different inputs.

We emphasize that these methods do not offer any inherent advantage in terms of computational efficiency. Apart from their beauty, their benefit lies in the possibility of gaining insights into the qualitative behavior of the Fresnel coefficients, which is important in developing a physical feeling of these relevant equations.

## II Fresnel formulas

Let two homogeneous isotropic semi-infinite media, described by complex refractive indices $`N_0`$ and $`N_1`$, be separated by a plane boundary. We assume an incident monochromatic, linearly polarized plane wave from medium 0, which makes an angle $`\theta _0`$ with the normal to the interface and has amplitude $`E^i`$. The electric field is either in the plane of incidence (denoted by subscript $``$) or perpendicular to the plane of incidence (subscript $``$). This wave splits into a reflected wave $`E^r`$ in medium 0, and a transmitted wave $`E^t`$ in medium 1 that makes an angle $`\theta _1`$ with the normal. The angles of incidence $`\theta _0`$ and refraction $`\theta _1`$ are related by Snell’s law:

$$N_0\mathrm{sin}\theta _0=N_1\mathrm{sin}\theta _1.$$
(1)
If media 0 and 1 are transparent (so that $`N_0`$ and $`N_1`$ are real numbers) and no total reflection occurs, the angles $`\theta _0`$ and $`\theta _1`$ are also real and the above picture of how a plane wave is reflected and refracted at the interface is simple. However, when either one or both media is absorbing, the angles $`\theta _0`$ and $`\theta _1`$ become, in general, complex and the discussion continues to hold only formally, but the physical picture of the fields becomes complicated ST63 .

The wave vectors of all waves lie in the plane of incidence and when the incident fields are $``$\- or $``$-polarized, all plane waves excited by the incident ones have the same polarization AZ87 . An arbitrarily polarized incident wave can be resolved into its $``$ and $``$ components, and each of them can be treated separately.

By demanding that the tangential components of $`𝐄`$ and $`𝐇`$ should be continuous across the boundary BO99 , and assuming nonmagnetic media, the reflection and transmission amplitudes are given by LE87

$$r_{}=\frac{E_{}^r}{E_{}^i}=\frac{N_0\mathrm{cos}\theta _0N_1\mathrm{cos}\theta _1}{N_0\mathrm{cos}\theta _0+N_1\mathrm{cos}\theta _1},$$
(2a)
$$r_{}=\frac{E_{}^r}{E_{}^i}=\frac{N_1\mathrm{cos}\theta _0N_0\mathrm{cos}\theta _1}{N_1\mathrm{cos}\theta _0+N_0\mathrm{cos}\theta _1},$$
(2b)
$$t_{}=\frac{E_{}^t}{E_{}^i}=\frac{2N_0\mathrm{cos}\theta _0}{N_0\mathrm{cos}\theta _0+N_1\mathrm{cos}\theta _1},$$
(2c)
$$t_{}=\frac{E_{}^t}{E_{}^i}=\frac{2N_0\mathrm{cos}\theta _0}{N_1\mathrm{cos}\theta _0+N_0\mathrm{cos}\theta _1},$$
(2d)
which are the Fresnel formulas. The physical contents of these coefficients are discussed in any optics textbook.

## III Graphical construction for the reflection coefficients

### III.1 General considerations

The geometrical method we outline here deals only with the case when media 0 and 1 are transparent. The refractive indices are then real numbers that we denote by $`n_0`$ and $`n_1`$. Before going into details we wish to show how the algebraic properties of the Fresnel reflection coefficients can be intimately linked to some elementary geometrical properties of an isosceles trapezoid.

The key point for our purposes is to note that the reflection coefficients can be written as

$$r=\frac{ab}{a+b},$$
(3)
where $`a`$ and $`b`$ are positive real numbers whose explicit form depend on the polarization. To visualize the algebraic properties of this quotient LI98  we propose to use the geometrical construction depicted in Fig. 1. Let us assume first (Fig. 1.a) that $`a>b`$: then $`r>0`$ and this coefficient can be inferred from an isosceles trapezoid with minor basis $`ab`$ and major basis $`a+b`$, since the quotient of such bases is precisely $`r`$. When $`a=b`$ (Fig. 1.b) the trapezoid degenerates in an isosceles triangle and $`r=0`$. Finally, when $`a<b`$, the numerator in $`r`$ is negative. Since a segment cannot have a negative length, we represent this case by plotting the bow tie of Fig. 1.c and we have then that $`r<0`$.

In the next section we shall illustrate how this simple construction allows for a complete determination of the reflection coefficients. Before we do that and to relate this interpretation with other previous results, we wish to note that any equation of the form (3) can always be expressed as

$$r=\frac{ab}{a+b}=\frac{\xi 1/\xi }{\xi +1/\xi }=\mathrm{tanh}\zeta ,$$
(4)
where

$$\xi =\sqrt{\frac{a}{b}}=\mathrm{exp}(\zeta ).$$
(5)
In spite of its simplicity, we think that this is a remarkable formula KH79 ; CO91 ; MO99 . It states that any reflection coefficient can be always expressed as a hyperbolic tangent, just as in special relativity the velocities are expressed in terms of the rapidity VG93 ; MO00 ; MO01 .

### III.2 Perpendicular polarization

The previous general reasoning suggests that Fresnel formulas can be seen from a purely geometrical viewpoint. To go one step further, and to quantify these ideas, we plot two concentric circumferences of radii $`n_0`$ and $`n_1`$ centered at the origin $`O`$, as shown in Fig. 2 (we need to take care only of the first quadrant). We assume $`n_0<n_1`$, which does not suppose any serious restriction.

For the case of polarization $``$ that we are considering, we draw in the circumference $`n_0`$ the radius that forms an angle $`\theta _0`$ with the horizontal. We denote by $`S_0`$ the point where this radius intersects the circumference. Next, we draw a horizontal line from $`S_0`$ that intersects the circumference $`n_1`$ at the point $`S_1`$. The radius $`OS_1`$ determines then the refraction angle $`\theta _1`$. A quick look at this figure shows that the projections on the vertical axis of the radii $`OS_0`$ and $`OS_1`$ are identical, in agreement with Snell’s law.

If the light is incident from medium 1 at angle $`\theta _1`$ we would obtain first $`S_1`$ and, in a completely analogous way, the corresponding pair $`S_0`$ and $`\theta _0`$.

When the point $`S_0`$ runs the quadrant $`n_0`$ (i.e., $`\theta _0`$ varies from 0 to $`\pi /2`$) the point $`S_1`$ runs the quadrant $`n_1`$ in such a way that $`\theta _1`$ varies from 0 to the critical angle $`\theta _c`$ (obviously, total internal reflection occurs only when the light is incident from the denser medium). This is a clear way of picturing the critical angle.

On the other hand, the projections on the horizontal axis of the radii $`OS_0`$ and $`OS_1`$ measure $`a=n_0\mathrm{cos}\theta _0`$ and $`b=n_1\mathrm{cos}\theta _1`$, respectively. The values of $`ab`$ and $`a+b`$ have been marked in Fig. 3 as bold segments. Since $`a<b`$ for every $`\theta _0`$, $`r_{}`$ is always negative and the trapezoid is a bow tie, according to our previous discussion. For $`\theta _0=0`$ the bow tie degenerates into two horizontal segments of lengths $`n_1n_0`$ and $`n_1+n_0`$, while for $`\theta _0=\pi /2`$ it reduces to two identical triangles.

As the angle of incidence increases, the minor basis grows while the major basis decreases. Therefore, the absolute value of $`r_{}`$ grows monotonically with the angle of incidence, up to its maximum value of 1 at grazing incidence.

Finally, the numerical value of $`r_{}`$ can be determined by a ruler. To this end, it suffices with constructing the right-angled triangle having as legs the bases of the previous bow tie. It is obvious that $`r_{}`$ coincides with the height of a similar triangle of unity basis, as shown in Fig. 3.

### III.3 Parallel polarization

The richer phenomenology of the $``$ polarization is clearly highlighted also by this graphical construction. The method is essentially the same as that for $``$ polarization. Once we are given the incidence angle $`\theta _0`$, we construct the refraction angle $`\theta _1`$ much in the same way.

It is clear from Eqs. (2a) and (2b) that $`r_{}`$ can be obtained from $`r_{}`$ by exchanging the refractive indices. In consequence, this suggests, as shown in Fig. 4, that now the radius $`OS_0`$ must be extended until it intersects the circumference $`n_1`$ at the point $`P_0`$. Similarly, we obtain the point $`P_1`$ as the intersection of the radius $`OS_1`$ with the circumference $`n_0`$. Obviously, the horizontal projections of $`OP_0`$ and $`OP_1`$ are $`a=n_1\mathrm{cos}\theta _0`$ and $`b=n_0\mathrm{cos}\theta _1`$, respectively and, as before, $`ab`$ and $`a+b`$ have been marked in Fig. 4 as bold segments. These segments are the bases of an isosceles trapezoid that appears shaded in the figure. The nonparallel sides have a length $`n_0`$ and form an angle $`\theta _1`$ with the major basis.

For $`\theta _0=0`$ the trapezoid degenerates into two horizontal segments of lengths $`n_1n_0`$ and $`n_1+n_0`$, as it happens for $``$ polarization. This reproduces the well-known fact that at normal incidence there is no physical difference between both basic polarizations, except for a sign.

As $`\theta _0`$ increases, the minor basis $`P_1P_0^{}`$ decreases, reaching the value 0 (so $`r_{}=0`$ also), which defines the Brewster angle. In this particular angle ($`\mathrm{tan}\theta _B=n_1/n_0`$) the points $`P_0`$ and $`P_1`$ are on the same vertical and, therefore, the trapezoid becomes a triangle. We think that this provides a remarkable way of visualizing this important angle (see Fig. 5). When the angle of incidence is further increased, $`r_{}`$ becomes negative. This can be seen in the fact that the trapezoid becomes a bow tie. Finally, at grazing incidence this bow tie is made from two identical isosceles triangles and then $`r_{}=1`$, as for the $``$ polarization. The numerical value of $`r_{}`$ can be determined by a ruler by the same procedure as before.

Before finishing, we wish to emphasize that, concerning the behavior of the corresponding transmission coefficients, this geometrical construction still applies, but its interpretation is more involved, because they do not behave like a hyperbolic function MO00 .

### III.4 Relation between basic polarizations

It is the purpose of this section to show how our approach interprets the quotient HE99

$$\frac{r_{}}{r_{}}=\frac{\mathrm{cos}(\theta _0\theta _1)}{\mathrm{cos}(\theta _0+\theta _1)}$$
(6)
as a simple symmetry in the plane. Azzam AZ79a ; AZ79b  has noticed that this relation can be recast so as to show a universal character (i.e, it is independent of the two media that define the interface), and it has proven to be of practical interest.

Let us denote by $`\{AB\}`$ the horizontal projection of the segment $`AB`$. From our previous discussion, we can recast the reflection coefficients as

$$r_{}=\frac{\{OS_0OS_1\}}{\{OS_0+OS_1\}}=\frac{S_1S_0}{\{OS\}},$$
(7a)
$$r_{}=\frac{\{OP_0OP_1\}}{\{OP_0+OP_1\}}=\frac{\{P_1P_0\}}{\{OP\}},$$
(7b)
where we have written $`OS_0+OS_1=OS`$ and $`OP_0+OP_1=OP`$. It is easy to check that $`OS`$ and $`OP`$ have the same length.

Next, we note that the four points considered until now, namely, $`S_0`$, $`S_1`$ and $`P_0`$, $`P_1`$, are the vertex of the sector of annulus shaded in Fig. 6. The triangles $`OP_0P_1`$ and $`OS_0S_1`$ are identical and can be obtained by a reflection through the bisecting line $`OB`$ of the sector. The two diagonals $`S_0S_1`$ and $`P_0P_1`$ have the same length and form between them an angle $`\theta _0+\theta _1`$. On the other hand, the bisecting line $`OB`$ forms with the horizontal axis an angle $`(\theta _0+\theta _1)/2`$ and it is a symmetry axis with respect to the pairs of points $`S_0`$ and $`P_1`$, $`P_0`$ and $`S_1`$, and $`P`$ and $`S`$. That is, $`OP`$ and $`OS`$ form the same angle $`\alpha `$ with $`OB`$, where $`\alpha `$ can be computed to be

$`\mathrm{tan}\alpha `$ $`=`$ $`{\displaystyle \frac{(n_1n_0)\mathrm{sin}[(\theta _0\theta _1)/2]}{(n_1+n_0)\mathrm{cos}[(\theta _0\theta _1)/2]}}`$ (8)
$`=`$ $`{\displaystyle \frac{n_1n_0}{n_1+n_0}}\mathrm{tan}[(\theta _0\theta _1)/2].`$
We thus conclude that the numerators in (7a) and (7b) are related by

$$\frac{S_1S_0}{\{P_1P_0\}}=\frac{1}{\mathrm{cos}(\theta _0+\theta _1)},$$
(9)
while for the denominators it holds

$$\frac{\{OP\}}{\{OS\}}=\frac{\mathrm{cos}[(\theta _0+\theta _1)/2+\alpha ]}{\mathrm{cos}[(\theta _0+\theta _1)/2\alpha ]}=\mathrm{cos}(\theta _0\theta _1).$$
(10)
This concludes the geometrical proof of Eq. (6) and shows that the coefficients $`r_{}`$ and $`r_{}`$ can be interpreted as quotients of horizontal projections of segments that are symmetric with respect to the bisecting line. As far as we know, this simple result has been never noticed in the literature.

## IV Concluding remarks

The method given in this paper provides a geometrical construction for getting the values of the Fresnel reflection coefficients by ruler and compass. These graphical methods appeal more readily to students than an analytical treatment.

The construction allows one to show at a simple glance the variation of these coefficients with the angle of incidence and the peculiarities of the parallel polarization when crossing the Brewster angle.

###### Acknowledgements.

We wish to thank B. Rose, F. Sánchez-Quesada and M. Sancho for a careful reading of the manuscript.


text:
# 1 Introduction

## 1 Introduction

We define a *two–dimensional polytope* $`𝒫`$ as a compact subset of $`^2`$ bounded by a simple, closed polygonal curve. $`𝒫`$ is called a *rational polytope* if all of its vertices have rational coordinates. We give explicit, polynomial–time computable (in the logarithm of the coordinates of the vertices) formulas for the number of integer points in any two–dimensional rational polytope and its integral dilations. We emphasize an expository flavor in this paper. In the current literature, there are either ‘nice’ formulas that do not appear to be polynomial–time computable \[BV, DR, KK, KP, P\], or there are polynomial–time computable algorithms without ‘nice’ formulas \[Ba\]. Asking for both seems to be asking for too much; but in $`^2`$ we show that we can have our cake and eat it, too.

To fix notation, let $`𝒫^{}`$ be the interior of $`𝒫`$, and $`\overline{𝒫}=𝒫`$ be the closure of $`𝒫`$. For $`t`$, let $`L(𝒫^{},t)=\mathrm{\#}\left(t𝒫^{}^2\right)`$ and $`L(\overline{𝒫},t)=\mathrm{\#}\left(t\overline{𝒫}^2\right)`$ be the number of lattice points in the interior and closure, respectively, of the dilated polytope $`t𝒫=\{(tx,ty):(x,y)𝒫\}`$. Ehrhart, who initiated the study of the lattice point count in dilated polytopes \[E\], proved that $`L(𝒫^{},t)`$ and $`L(\overline{𝒫},t)`$ are quasipolynomials in $`t`$. A *quasipolynomial* is an expression of the form $`c_n(t)t^n+\mathrm{}+c_1(t)t+c_0(t)`$, where $`c_0,\mathrm{},c_n`$ are periodic functions in $`t`$.

A natural first step is to fix a triangulation of $`𝒫`$, which reduces our problem to counting integer points in rational *triangles*. However, this procedure merits some remarks. First, triangulation is not easy, but there has been remarkable progress recently, so that we can triangulate a convex polygon with $`n`$ vertices in roughly $`n`$ steps \[C\]. On the other hand, we are concerned with the efficiency of our formulas with respect to the coordinates of the vertices of $`𝒫`$, and not the number of vertices.

Another point of non–trivial significance is the number of lattice points on rational line segments, namely the boundary of our triangles. Although this is considerable easier than enumerating lattice points in 2–dimensional regions, it is still non–trivial and has only recently been completely solved \[BR, T\]. It is amusing that counting lattice points on line segments gave rise to links with the Frobenius coin–exchange problem and the number of representations of an integer by a linear form.

After triangulating $`𝒫`$, we can further simplify the picture by embedding an arbitrary rational triangle in a rational rectangle:

Since rectangles are easy to deal with, the problem reduces to finding a formula for a right–angled rational triangle. Such a formula is given in Section 2 using generating functions; this derivation is a refinement of a previously introduced method \[Be\]. We find (Section 3) that the basic building blocks of the lattice point count formulas for any two–dimensional rational polytope are the sawtooth function

$$((x)):=x[x]\frac{1}{2}$$

and the Dedekind–Rademacher sum

$$\sigma (a,b,t):=\underset{k=0}{\overset{b1}{}}\left(\left(\frac{ak+t}{b}\right)\right)\left(\left(\frac{k}{b}\right)\right).$$
(1)
Here $`a`$ and $`b`$ are integers, and $`t`$ is a real number. We use the name Dedekind–Rademacher sum in a somewhat lenient fashion; often $`((x))`$ is defined to be 0 if $`x`$, also Rademacher’s original definition is \[Di, Me, Ra\]

$$s(a,b;x,y):=\underset{k=0}{\overset{b1}{}}\left(\left(\frac{a(k+y)}{b}+x\right)\right)\left(\left(\frac{k+y}{b}\right)\right).$$

Here $`a`$ and $`b`$ are integers, whereas $`x`$ and $`y`$ are real. However, it is clear that the different use of $`((\mathrm{}))`$ only results in a difference of the arithmetic sums in a trivial term. Also, $`\sigma `$ and $`s`$ are strongly linked via

$$\sigma (a,b,t)=s(a,b;\frac{t}{a},0)$$

and

$$s(a,b;x,y)=\sigma (a,b,ay+bx)+\frac{y}{b}((ya+xb)).$$

We chose to use $`\sigma `$ rather than $`s`$ because of its natural appearance in our formulas. There exists a two–term reciprocity law for these sums \[K, Ra\], which enables us to compute $`\sigma (a,b,t)`$ in polynomial time, similar in spirit to the Euclidean algorithm. From this fact we conclude that our lattice point enumerator for $`𝒫`$ is polynomial–time computable (Section 4).

As a by–product of our formulas, we rederive in Section 5 two reciprocity laws as corollaries: the two–term law for the classical Dedekind sum (\[De\], Chapter 2 of \[RG\]), and a two–term law for generalized Dedekind sums due to Gessel \[G\]. In fact, our approach shows that Gessel’s reciprocity law is a special case of the reciprocity law for Dedekind–Rademacher sums, a theorem due to Rademacher \[Ra\].

## 2 Generating functions

In \[Be\], the first author used the residue theorem to count lattice points in certain tetrahedra. Here we adjust and expand these methods to the rectangular triangles we reduced the discussion to in the introduction. Such a rectangular triangle $`𝒯`$ is given as a subset of $`^2`$ consisting of all points $`(x,y)`$ satisfying

$$x\frac{a}{d},y\frac{b}{d},ex+fyr$$

for some integers $`a,b,d,e,f,r`$ with $`ea+fbrd`$. Because the lattice point count is invariant under horizontal and vertical integer translation and under flipping about x- or y-axis, we may assume that $`a,b,d,e,f,r0`$ and $`a,b<d`$. Let’s further factor out the greatest common divisor $`c`$ of $`e`$ and $`f`$, so that $`e=cp`$ and $`f=cq`$, where $`p`$ and $`q`$ are relatively prime. Hence

$$𝒯=\{(x,y)^2:x\frac{a}{d},y\frac{b}{d},cpx+cqyr\}.$$
(2)
To derive a formula for $`L(\overline{𝒯},t)`$ we interpret, similarly as in \[Be\],

$$L(\overline{𝒯},t)=\mathrm{\#}\{(m,n)^2:m\frac{ta}{d},n\frac{tb}{d},cpm+cqntr\}$$

as the Taylor coefficient of $`z^{tr}`$ of the function

$`\left({\displaystyle \underset{m\left[\frac{ta1}{d}\right]+1}{}}z^{cpm}\right)\left({\displaystyle \underset{n\left[\frac{tb1}{d}\right]+1}{}}z^{cqn}\right)\left({\displaystyle \underset{k0}{}}z^k\right)={\displaystyle \frac{z^{\left(\left[\frac{ta1}{d}\right]+1\right)cp}}{1z^{cp}}}{\displaystyle \frac{z^{\left(\left[\frac{tb1}{d}\right]+1\right)cq}}{1z^{cq}}}{\displaystyle \frac{1}{1z}}`$
$`={\displaystyle \frac{z^{u+v}}{\left(1z^{cp}\right)\left(1z^{cq}\right)(1z)}},`$ (3)
where we introduced, for ease of notation,

$$u:=\left(\left[\frac{ta1}{d}\right]+1\right)cp\text{ and }v:=\left(\left[\frac{tb1}{d}\right]+1\right)cq.$$
(4)
We present two methods on how to extract the lattice point count from this generating function: partial fractions and the residue theorem. Both are inspired by works on generalized Dedekind sums, the first one by Gessel \[G\], the latter one by Zagier \[Z\]. In fact, both ways are completely equivalent, since our generating function is rational. However, to please both algebraically and analytically minded readers, we give two proofs of the following

###### Proposition 2.1

For the rectangular rational triangle $`𝒯`$ given by (2),

$`L(\overline{𝒯},t)={\displaystyle \frac{1}{2c^2pq}}\left(truv\right)^2+{\displaystyle \frac{1}{2}}\left(truv\right)\left({\displaystyle \frac{1}{cp}}+{\displaystyle \frac{1}{cq}}+{\displaystyle \frac{1}{c^2pq}}\right)`$
$`+{\displaystyle \frac{1}{4}}\left(1+{\displaystyle \frac{1}{cp}}+{\displaystyle \frac{1}{cq}}\right)+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{c^2pq}}\right)`$
$`+\left({\displaystyle \frac{1}{2cp}}+{\displaystyle \frac{1}{2cq}}{\displaystyle \frac{u+vtr}{c^2pq}}\right){\displaystyle \underset{\lambda ^c=1\lambda }{}}{\displaystyle \frac{\lambda ^{tr}}{1\lambda }}{\displaystyle \frac{1}{c^2pq}}{\displaystyle \underset{\lambda ^c=1\lambda }{}}{\displaystyle \frac{\lambda ^{tr+1}}{(1\lambda )^2}}`$
$`+{\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^{vtr}}{\left(1\lambda ^{cq}\right)\left(1\lambda \right)}}+{\displaystyle \frac{1}{cq}}{\displaystyle \underset{\lambda ^{cq}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^{utr}}{\left(1\lambda ^{cp}\right)\left(1\lambda \right)}},`$
where $`u`$ and $`v`$ are given by (4).

It will be useful to have the Laurent expansion of the factors of our generating function. The following lemma will provide a bridge between the residue method and the partial fraction method.

###### Lemma 2.2

Let $`a,b`$ be positive integers, and $`\lambda ^a=1`$. Then

$$\frac{1}{1z^{ab}}=\frac{\lambda }{ab}(z\lambda )^1+\frac{ab1}{2ab}+O(z\lambda ).$$

Proof. First,

$$\text{Res}\left(\frac{1}{1z^{ab}},z=\lambda \right)=\underset{z\lambda }{lim}\frac{z\lambda }{1z^{ab}}=\frac{\lambda }{ab}.$$

For $`ab=1`$, the statement is trivial, so we may assume $`ab2`$. Then the constant term of the Laurent series of $`\frac{1}{1z^{ab}}`$ can be computed as

$`\underset{z\lambda }{lim}\left({\displaystyle \frac{1}{1z^{ab}}}+{\displaystyle \frac{\lambda }{ab(z\lambda )}}\right)=\underset{z\lambda }{lim}{\displaystyle \frac{ab(z\lambda )+\lambda \left(1z^{ab}\right)}{ab(z\lambda )\left(1z^{ab}\right)}}=\underset{z\lambda }{lim}{\displaystyle \frac{abab\lambda z^{ab1}}{ab\left(1z^{ab}(z\lambda )abz^{ab1}\right)}}`$
$`=\underset{z\lambda }{lim}{\displaystyle \frac{\lambda (ab1)z^{ab2}}{2abz^{ab1}(z\lambda )ab(ab1)z^{ab2}}}={\displaystyle \frac{ab1}{2ab}}.`$
$`\mathrm{}`$

First proof of Proposition 2.1 (partial fractions). To make life easier, we translate the coefficient of $`z^{tr}`$ of our generating function, which yields the lattice point count, to the constant coefficient of the function

$$\frac{z^{u+vtr}}{\left(1z^{cp}\right)\left(1z^{cq}\right)(1z)}.$$
(5)
This is a proper rational function because

$$cp\frac{a}{d}+cq\frac{b}{d}r$$

($`𝒯\mathrm{}`$!), which implies

$$u+vtrcpcq1=\left[\frac{ta1}{d}\right]cp+\left[\frac{tb1}{d}\right]cqtr1<\frac{ta}{d}cp+\frac{tb}{d}cqtr11.$$

By expanding (5) into partial fractions

$`{\displaystyle \frac{z^{u+vtr}}{\left(1z^{cp}\right)\left(1z^{cq}\right)(1z)}}=`$
$`{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{A_\lambda }{z\lambda }}+{\displaystyle \underset{\lambda ^{cq}=1\lambda ^c}{}}{\displaystyle \frac{B_\lambda }{z\lambda }}+{\displaystyle \underset{\lambda ^c=1\lambda }{}}\left({\displaystyle \frac{C_\lambda }{z\lambda }}+{\displaystyle \frac{D_\lambda }{(z\lambda )^2}}\right)+{\displaystyle \underset{k=1}{\overset{3}{}}}{\displaystyle \frac{E_k}{(z1)^k}}+{\displaystyle \underset{k=1}{\overset{truv}{}}}{\displaystyle \frac{F_k}{z^k}},`$
we can compute $`L(\overline{𝒯},t)`$ as the constant coefficient of the right–hand side:

$$L(\overline{𝒯},t)=\underset{\lambda ^{cp}=1\lambda ^c}{}\frac{A_\lambda }{\lambda }\underset{\lambda ^{cq}=1\lambda ^c}{}\frac{B_\lambda }{\lambda }+\underset{\lambda ^c=1\lambda }{}\left(\frac{C_\lambda }{\lambda }+\frac{D_\lambda }{\lambda ^2}\right)E_1+E_2E_3.$$
(6)
The computation of the coefficients $`A_\lambda `$ for $`\lambda ^{cp}=1\lambda ^c`$ is straightforward:

$$A_\lambda =\underset{z\lambda }{lim}\frac{(z\lambda )z^{u+vtr}}{\left(1z^{cp}\right)\left(1z^{cq}\right)(1z)}=\frac{\lambda ^{vtr}}{\left(1\lambda ^{cq}\right)(1\lambda )}\underset{z\lambda }{lim}\frac{(z\lambda )}{1z^{cp}}=\frac{\lambda ^{vtr+1}}{cp\left(1\lambda ^{cq}\right)(1\lambda )}.$$

Similarly, we obtain for the $`cq`$th roots of unity $`\lambda ^{cq}=1\lambda ^c`$

$$B_\lambda =\frac{\lambda ^{utr+1}}{cq\left(1\lambda ^{cp}\right)(1\lambda )}.$$

The coefficients $`D_\lambda `$ and $`C_\lambda `$ are the two leading coefficients of the Laurent series of (5) about a nontrivial $`c`$th root of unity $`\lambda `$. Using Lemma 2.2, they are easily seen to be

$$D_\lambda =\frac{\lambda ^{tr+2}}{c^2pq(1\lambda )}$$

and

$$C_\lambda =\left(\frac{1}{2cp}\frac{1}{2cq}+\frac{u+vtr+1}{c^2pq}\right)\frac{\lambda ^{tr+1}}{1\lambda }+\frac{\lambda ^{tr+2}}{c^2pq(1\lambda )^2}.$$

Finally, we obtain the coefficients $`E_k`$ from the Laurent series of (5) about $`z=1`$ (by hand or, preferably, using a computer algebra system) as

$$E_3=\frac{1}{c^2pq},E_2=\frac{u+vtr+1}{c^2pq}+\frac{1}{2cp}+\frac{1}{2cq},$$

and

$`E_1={\displaystyle \frac{(u+vtr)^2}{2c^2pq}}+{\displaystyle \frac{u+vtr}{2}}\left({\displaystyle \frac{1}{c^2pq}}+{\displaystyle \frac{1}{cp}}+{\displaystyle \frac{1}{cq}}\right)+{\displaystyle \frac{1}{4}}\left({\displaystyle \frac{1}{cp}}+{\displaystyle \frac{1}{cq}}1\right){\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{1}{c^2pq}}+{\displaystyle \frac{q}{p}}\right).`$
Putting these ingredients into (6) yields the statement. $`\mathrm{}`$

Second proof of Proposition 2.1 (residue theorem). The sought–after Taylor coefficient of (3) can be shifted to a residue:

$$L(\overline{𝒯},t)=\text{Res}\left(\frac{z^{u+vtr1}}{\left(1z^{cp}\right)\left(1z^{cq}\right)\left(1z\right)},z=0\right)$$
(7)
If the right–hand side of (7) counts the lattice points in $`t𝒯`$, then what we have to do is compute the other residues of

$$f(z):=\frac{z^{u+vtr1}}{\left(1z^{cp}\right)\left(1z^{cq}\right)\left(1z\right)},$$

and use the residue theorem for the sphere $`\left\{\mathrm{}\right\}`$. Aside from 0, $`f`$ has poles at all $`cp`$th and $`cq`$th roots of unity; note that the nonemptyness of $`𝒯`$ implies Res($`f(z),z=\mathrm{}`$) = 0.

The residue at $`z=1`$ can be easily calculated as

$`\text{Res}\left(f(z),z=1\right)=\text{Res}\left(e^zf(e^z),z=0\right)={\displaystyle \frac{1}{2c^2pq}}\left(u+vtr\right)^2`$
$`+{\displaystyle \frac{1}{2}}\left(u+vtr\right)\left({\displaystyle \frac{1}{cp}}+{\displaystyle \frac{1}{cq}}+{\displaystyle \frac{1}{c^2pq}}\right){\displaystyle \frac{1}{4}}\left(1+{\displaystyle \frac{1}{cp}}+{\displaystyle \frac{1}{cq}}\right){\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{c^2pq}}\right).`$
It remains to compute the residues at the nontrivial roots of unity. Let $`\lambda `$ be a nontrivial $`c`$th roots of unity. Putting the Laurent expansions of the different factors of $`f`$ together, the residue of $`f`$ at $`\lambda `$ can be easily derived via Lemma 2.2 as

$$\text{Res}\left(f(z),z=\lambda \right)=\left(\frac{u+vtr}{c^2pq}+\frac{1}{2cp}+\frac{1}{2cq}\right)\frac{\lambda ^{tr}}{1\lambda }+\frac{\lambda ^{tr+1}}{c^2pq(1\lambda )^2}.$$

Note that we have to add this expression over all nontrivial $`c`$th roots of unity.

Now let $`\lambda ^{cp}=1\lambda ^c`$. Since $`p`$ and $`q`$ are relatively prime, $`f`$ has a simple pole at $`\lambda `$, whose residue can be determined easily using Lemma 2.2:

$$\text{Res}\left(f(z),z=\lambda \right)=\frac{\lambda ^{vtr1}}{\left(1\lambda ^{cq}\right)\left(1\lambda \right)}\text{Res}\left(\frac{1}{1\lambda ^{cp}},z=\lambda \right)=\frac{\lambda ^{vtr}}{cp\left(1\lambda ^{cq}\right)\left(1\lambda \right)}.$$

Again, we have to add up all these $`\lambda `$’s. Finally, we obtain a similar expression for the $`cq`$th roots of unity, and the statement of the proposition follows by rewriting (7) by means of the residue theorem. $`\mathrm{}`$

In the following section, we will further describe the finite sums appearing in the lattice point count operators; consequently, we will be able to make statements about their computational complexity.

## 3 Using the Dedekind–Rademacher sums as building blocks

We will now take a closer look at the finite sums over roots of unity appearing in Proposition 2.1, namely,

$$\frac{1}{cp}\underset{\lambda ^{cp}=1\lambda ^c}{}\frac{\lambda ^w}{\left(1\lambda ^{cq}\right)\left(1\lambda \right)}$$

for some integers $`c,p,q,w`$, where $`p`$ and $`q`$ are relatively prime. The fact that this is a finite Fourier series in $`w`$ and the appearance of two factors in the denominator suggest the use of the well–known Convolution Theorem for finite Fourier series:

###### Theorem 3.1

Let $`f(t)={\displaystyle \frac{1}{N}}{\displaystyle \underset{\lambda ^N=1}{}}a_\lambda \lambda ^t`$ and $`g(t)={\displaystyle \frac{1}{N}}{\displaystyle \underset{\lambda ^N=1}{}}b_\lambda \lambda ^t`$. Then

$$\frac{1}{N}\underset{\lambda ^N=1}{}a_\lambda b_\lambda \lambda ^t=\underset{m=0}{\overset{N1}{}}f(tm)g(m).$$

$`\mathrm{}`$

The key ingredient to be able to apply this theorem to our case is

###### Lemma 3.2

For $`p,t`$,

$$\frac{1}{p}\underset{\lambda ^p=1\lambda }{}\frac{\lambda ^t}{\lambda 1}=\left(\left(\frac{t}{p}\right)\right)+\frac{1}{2p}.$$

Recall that $`((x))=x[x]1/2`$. This lemma is well–known (see, e.g., \[RG\], p. 14), however, for sake of completeness we give a short proof based on the methods of section 2:

Proof. Consider the interval $`:=[0,\frac{1}{p}]`$, viewed as a one–dimensional polytope. Then the lattice point count in the dilated interval is clearly

$$L(\overline{},t)=\left[\frac{t}{p}\right]+1.$$
(8)
On the other hand, we can write this number, by applying the ideas in section 2, as

$$L(\overline{},t)=\text{Res}\left(\frac{z^{t1}}{\left(1z^p\right)\left(1z\right)},z=0\right).$$

(Equivalently, we could expand this generating function into partial fractions.) Using again the residue theorem, this can be rewritten as

$$L(\overline{},t)=\frac{t}{p}+\frac{1}{2p}+\frac{1}{2}\frac{1}{p}\underset{\lambda ^p=1\lambda }{}\frac{\lambda ^t}{\lambda 1}.$$
(9)
Comparing (8) with (9) yields the statement. $`\mathrm{}`$

###### Corollary 3.3

For $`c,p,q,t,(p,q)=1`$,

$$\frac{1}{cp}\underset{\lambda ^{cp}=1\lambda ^c}{}\frac{\lambda ^t}{1\lambda ^{cq}}=\{\begin{array}{cc}\left(\left(\frac{q^1t}{cp}\right)\right)\frac{1}{2p}\hfill & \text{ if }c|t\hfill \\ 0\hfill & \text{ otherwise. }\hfill \end{array}$$

Here, $`qq^11`$ mod $`p`$.

Proof. If $`c|t`$, write $`t=cw`$ to obtain

$`{\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^t}{1\lambda ^{cq}}}={\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^{cw}}{1\lambda ^{cq}}}={\displaystyle \frac{1}{p}}{\displaystyle \underset{\lambda ^p=1\lambda }{}}{\displaystyle \frac{\lambda ^w}{1\lambda ^q}}={\displaystyle \frac{1}{p}}{\displaystyle \underset{\lambda ^p=1\lambda }{}}{\displaystyle \frac{\lambda ^{q^1w}}{1\lambda }}`$
$`\stackrel{()}{=}\left(\left({\displaystyle \frac{q^1w}{p}}\right)\right){\displaystyle \frac{1}{2p}}=\left(\left({\displaystyle \frac{q^1t}{cp}}\right)\right){\displaystyle \frac{1}{2p}}.`$
Here, $`()`$ follows from Lemma 3.2. If $`c`$ does not divide $`t`$, let $`\xi =e^{2\pi i/cp}`$. Then

$`{\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^t}{1\lambda ^{cq}}}={\displaystyle \frac{1}{cp}}{\displaystyle \underset{m=1}{\overset{p1}{}}}{\displaystyle \underset{n=0}{\overset{c1}{}}}{\displaystyle \frac{\xi ^{(mc+np)t}}{1\xi ^{(mc+np)cq}}}={\displaystyle \frac{1}{cp}}{\displaystyle \underset{n=0}{\overset{c1}{}}}\xi ^{npt}{\displaystyle \underset{m=1}{\overset{p1}{}}}{\displaystyle \frac{\xi ^{mct}}{1\xi ^{mc^2q}}}=0.`$
$`\mathrm{}`$

###### Corollary 3.4

For $`c,p,q,t,(p,q)=1`$,

$$\frac{1}{cp}\underset{\lambda ^{cp}=1\lambda ^c}{}\frac{\lambda ^t}{\left(1\lambda ^{cq}\right)\left(1\lambda \right)}=\sigma (q,p,\frac{t}{c})\left(\left(\frac{t}{cp}\right)\right)+\frac{1}{2p}\left(\left(\frac{t}{c}\right)\right).$$

Proof. We will repeatedly use the periodicity of the sawtooth function. One consequence is, for $`p,x`$,

$$\underset{m=0}{\overset{p1}{}}\left(\left(\frac{m+x}{p}\right)\right)=((x)),$$
(10)
the proof of which is left as an exercise (\[RG\], p. 4). Now by Lemma 3.2,

$`{\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda \right)}}={\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda \right)}}{\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^c=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda \right)}}`$
$`=\left(\left({\displaystyle \frac{t}{cp}}\right)\right){\displaystyle \frac{1}{2cp}}{\displaystyle \frac{1}{p}}\left(\left(\left({\displaystyle \frac{t}{c}}\right)\right){\displaystyle \frac{1}{2c}}\right)=\left(\left({\displaystyle \frac{t}{cp}}\right)\right)+{\displaystyle \frac{1}{p}}\left(\left({\displaystyle \frac{t}{c}}\right)\right).`$
Finally we use the Convolution Theorem 3.1 and Corollary 3.3 to obtain

$`{\displaystyle \frac{1}{cp}}{\displaystyle \underset{\lambda ^{cp}=1\lambda ^c}{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^{cq}\right)\left(1\lambda \right)}}=`$
$`={\displaystyle \underset{\genfrac{}{}{0pt}{}{m=0}{c|m}}{\overset{cp1}{}}}\left(\left(\left({\displaystyle \frac{q^1m}{cp}}\right)\right){\displaystyle \frac{1}{2p}}\right)\left(\left(\left({\displaystyle \frac{(tm)}{cp}}\right)\right)+{\displaystyle \frac{1}{p}}\left(\left({\displaystyle \frac{(tm)}{c}}\right)\right)\right)`$
$`={\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{q^1k}{p}}\right)\right)\left(\left({\displaystyle \frac{k}{p}}{\displaystyle \frac{t}{cp}}\right)\right){\displaystyle \frac{1}{p}}{\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{q^1k}{p}}\right)\right)\left(\left({\displaystyle \frac{t}{c}}\right)\right)`$
$`+{\displaystyle \frac{1}{2p}}{\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{k}{p}}{\displaystyle \frac{t}{cp}}\right)\right){\displaystyle \frac{1}{2p^2}}{\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{t}{c}}\right)\right)`$
$`\stackrel{(\text{10})}{=}{\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{k}{p}}\right)\right)\left(\left({\displaystyle \frac{qk}{p}}{\displaystyle \frac{t}{cp}}\right)\right)+{\displaystyle \frac{1}{2p}}\left(\left({\displaystyle \frac{t}{c}}\right)\right)+{\displaystyle \frac{1}{2p}}\left(\left({\displaystyle \frac{t}{c}}\right)\right){\displaystyle \frac{1}{2p}}\left(\left({\displaystyle \frac{t}{c}}\right)\right)`$
$`\stackrel{(\text{10})}{=}{\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{k}{p}}\right)\right)\left(\left({\displaystyle \frac{qk}{p}}{\displaystyle \frac{t}{cp}}\right)\right)\left(\left({\displaystyle \frac{t}{cp}}\right)\right)+{\displaystyle \frac{1}{2p}}\left(\left({\displaystyle \frac{t}{c}}\right)\right).`$
The statement follows now by definition of the Dedekind–Rademacher sum (1). $`\mathrm{}`$

This corollary describes the finite sums in Proposition 2.1. One of them actually turns out to be of an even simpler form. To show this, we first need to rewrite Proposition 2.1 for the special case where $`𝒯`$ has the origin as a vertex:

###### Proposition 3.5

For the rectangular rational triangle $`𝒯`$ given by (2) with $`a=b=0`$, $`c=r=1`$, and $`p`$ and $`q`$ relatively prime,

$`L(\overline{𝒯},t)={\displaystyle \frac{t^2}{2pq}}+{\displaystyle \frac{t}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right)+{\displaystyle \frac{1}{4}}+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{pq}}\right)`$
$`\sigma (q,p,t)\sigma (p,q,t)\left(\left({\displaystyle \frac{t}{p}}\right)\right)\left(\left({\displaystyle \frac{t}{q}}\right)\right).`$
Proof. Proposition 2.1 gives for this special case

$`L(\overline{𝒯},t)={\displaystyle \frac{t^2}{2pq}}+{\displaystyle \frac{t}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right)+{\displaystyle \frac{1}{4}}\left(1+{\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}\right)+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{pq}}\right)`$
$`+{\displaystyle \frac{1}{p}}{\displaystyle \underset{\lambda ^p=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^q\right)\left(1\lambda \right)}}+{\displaystyle \frac{1}{q}}{\displaystyle \underset{\mu ^q=1\mu }{}}{\displaystyle \frac{\mu ^t}{\left(1\mu ^p\right)\left(1\mu \right)}}.`$
The statement follows now with Corollary 3.4. $`\mathrm{}`$

We use this Proposition to show

###### Lemma 3.6

For $`p,t`$,

$$\sigma (1,p,t)=\underset{k=0}{\overset{p1}{}}\left(\left(\frac{k+t}{p}\right)\right)\left(\left(\frac{k}{p}\right)\right)=\frac{p}{24}+\frac{1}{6p}+\frac{p}{2}\left(\left(\frac{t}{p}\right)\right)^2.$$

Proof. Consider the triangle $`\mathrm{\Delta }:=\{(x,y)^2:x+py1\}`$ and its integer dilates. By summing over vertical line segments in the triangle, we obtain

$`L(\mathrm{\Delta },t)={\displaystyle \underset{m=0}{\overset{\left[\frac{t}{p}\right]}{}}}(tpm+1)=(t+1)\left(\left[{\displaystyle \frac{t}{p}}\right]+1\right){\displaystyle \frac{p}{2}}\left[{\displaystyle \frac{t}{p}}\right]\left(\left[{\displaystyle \frac{t}{p}}\right]+1\right)`$
$`={\displaystyle \frac{t^2}{2p}}+\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{2}}\right)t+{\displaystyle \frac{1}{2}}+{\displaystyle \frac{p}{8}}\left(\left({\displaystyle \frac{t}{p}}\right)\right){\displaystyle \frac{p}{2}}\left(\left({\displaystyle \frac{t}{p}}\right)\right)^2.`$ (11)
On the other hand, we can compute the same number via Proposition 3.5:

$$L(\mathrm{\Delta },t)=\frac{t^2}{2p}+\frac{t}{2}\left(\frac{2}{p}+1\right)+\frac{1}{4}+\frac{1}{12}\left(p+\frac{2}{p}\right)\sigma (1,p,t)\frac{1}{4}\left(\left(\frac{t}{p}\right)\right)+\frac{1}{2}.$$
(12)
Again we used (10). Equating (11) with (12) yields the statement. $`\mathrm{}`$

Using these ingredients, we can finally restate Proposition 2.1 as our main theorem:

###### Theorem 3.7

For the rectangular rational triangle $`𝒯`$ given by (2),

$`L(\overline{𝒯},t)={\displaystyle \frac{1}{2c^2pq}}(truv)^2+(truv)\left({\displaystyle \frac{1}{2cp}}+{\displaystyle \frac{1}{2cq}}+{\displaystyle \frac{1}{c^2pq}}+{\displaystyle \frac{1}{cpq}}\left(\left({\displaystyle \frac{tr}{c}}\right)\right)\right)`$
$`+{\displaystyle \frac{1}{4}}+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}\right){\displaystyle \frac{1}{24pq}}+{\displaystyle \frac{1}{c^2pq}}+\left({\displaystyle \frac{1}{2p}}+{\displaystyle \frac{1}{2q}}\right)\left(\left({\displaystyle \frac{tr}{c}}\right)\right)`$
$`\left(\left({\displaystyle \frac{trv}{cp}}\right)\right)\left(\left({\displaystyle \frac{tru}{cq}}\right)\right)+\left({\displaystyle \frac{1}{cpq}}{\displaystyle \frac{1}{2p}}{\displaystyle \frac{1}{2q}}\right)\left(\left({\displaystyle \frac{tr}{c}}\right)\right)`$
$`+{\displaystyle \frac{1}{cpq}}\left(\left({\displaystyle \frac{tr1}{c}}\right)\right)+{\displaystyle \frac{1}{2pq}}\left(\left({\displaystyle \frac{tr1}{c}}\right)\right)^2\sigma (q,p,{\displaystyle \frac{trv}{c}})\sigma (p,q,{\displaystyle \frac{tru}{c}}).`$
Here $`u`$ and $`v`$ are given by (4).

Proof. By Lemma 3.2,

$$\frac{1}{c}\underset{\lambda ^c=1\lambda }{}\frac{\lambda ^w}{1\lambda }=\left(\left(\frac{w}{c}\right)\right)\frac{1}{2c}.$$
(13)
By Corollary 3.4 and Lemma 3.6,

$`{\displaystyle \frac{1}{c}}{\displaystyle \underset{\lambda ^c=1\lambda }{}}{\displaystyle \frac{\lambda ^w}{(1\lambda )^2}}=\sigma (1,cw)\left(\left({\displaystyle \frac{w}{c}}\right)\right){\displaystyle \frac{1}{4c}}`$
$`={\displaystyle \frac{c}{24}}{\displaystyle \frac{5}{12c}}\left(\left({\displaystyle \frac{w}{c}}\right)\right){\displaystyle \frac{c}{2}}\left(\left({\displaystyle \frac{w}{c}}\right)\right)^2.`$ (14)
Now simplify the identity in Proposition 2.1 by means of (13), (14), and Corollary 3.4. $`\mathrm{}`$

We mention the work of Brion and Vergne \[BV\] on rational polytopes, where they give formulas for the lattice point enumerator of a convex rational polytope in terms of certain Todd differential operators. These are interesting connections to topology. The salient difference in approaches lies in our explicit use of Dedekind–Rademacher sums and their computational efficiency. Although \[BV\] offer an approach which might eventually yield similar results, the analysis of the equivalence between our different approaches would be the content of another paper. The results in \[BV, main result on p. 831\] are coordinate–free, and have their theoretical merits. In contrast our results are coordinatized and are useful in the context of computer–related applications.

## 4 Remarks and consequences

Rademacher’s original definition \[Ra\] of his generalization of the Dedekind sum is

$$S(a,b;x,y):=\frac{1}{b}\underset{k=0}{\overset{b1}{}}\left(\left(\frac{a(k+y)}{b}+x\right)\right)^{}\left(\left(\frac{k+y}{b}\right)\right)^{},$$

defined for $`a,b,x,y`$. Here,

$$((x))^{}:=\{\begin{array}{cc}((x))\hfill & \text{ if }x\hfill \\ 0\hfill & \text{ if }x\hfill \end{array}$$

is the sawtooth function which also appears in the classical Dedekind sum $`S(a,b;0,0)`$. The impact of the slightly different definition of the sawtooth function is not crucial for our lattice point count formula. In fact, it is easy to see that

$$\sigma (a,b,t)=S(a,b;\frac{t}{b},0)\frac{1}{2}\left(\left(\frac{t}{b}\right)\right).$$
(15)
An important property of $`S(a,b;x,y)`$ is Rademacher’s reciprocity law \[Ra\]

$`S(a,b;x,y)+S(b,a;y,x)=`$
$`=\{\begin{array}{cc}\frac{1}{4}+\frac{1}{12}\left(\frac{a}{b}+\frac{1}{ab}+\frac{b}{a}\right)\hfill & \text{ if both }x,y\hfill \\ ((x))^{}((y))^{}+\frac{1}{2}\left(\frac{a}{b}\psi _2(y)+\frac{1}{ab}\psi _2(ay+bx)+\frac{b}{a}\psi _2(x)\right)\hfill & \text{ otherwise, }\hfill \end{array}`$
where

$$\psi _2(x):=(x[x])^2(x[x])+\frac{1}{6}$$

is the periodic second Bernoulli polynomial. The equivalent reciprocity law for $`\sigma (a,b,t)`$ was first presented in \[K\]; we will rediscover it in the last section.

Among other things, Rademacher’s reciprocity law allows us to compute $`S(a,b;x,y)`$ (and hence $`\sigma (a,b,t)`$, the nontrivial part of our lattice point count formulas) in polynomial time, by means of a Euclidean algorithm using the first two variables: simply note that we can replace $`a`$ in $`S(a,b;x,y)`$ by the least residue of $`a`$ modulo $`b`$. It is amusing to note that $`\sigma (a,b,t)`$ appears in the multiplier system of a weight–0 modular form \[Ro\].

To complete the picture for an arbitrary two–dimensional rational polytope $`𝒫`$, we return to the statements in the introduction. After triangulating $`𝒫`$, the problem reduces to rational rectangles and the rectangular triangles which were treated above. A lattice point count formula for a rational rectangle $``$ is easy to obtain: suppose $``$ has vertices $`(\frac{a_1}{d},\frac{a_2}{d}),(\frac{b_1}{d},\frac{a_2}{d}),(\frac{b_1}{d},\frac{b_2}{d}),(\frac{a_1}{d},\frac{b_2}{d})`$, with $`a_j<b_j`$, then it is not hard to see that

$$L(\overline{},t)=\left(\left[\frac{tb_1}{d}\right]\left[\frac{ta_11}{d}\right]\right)\left(\left[\frac{tb_2}{d}\right]\left[\frac{ta_21}{d}\right]\right).$$

Together with the above established remark on computability of $`\sigma (a,b,t)`$, we summarize some statements in

###### Theorem 4.1

Let $`𝒫`$ be a two–dimensional rational polytope. The coefficients of $`L(\overline{𝒫},t)`$ can be written in terms of the sawtooth function $`((\mathrm{}))`$ and the Dedekind–Rademacher sum $`\sigma (a,b,t)`$. Consequently, the formula given by Theorem 3.7 for the lattice point count operator can be computed in polynomial time in the logarithm of the denominators of the vertices of $`𝒫`$. $`\mathrm{}`$

Barvinok \[Ba\] showed that for any fixed dimension the lattice point enumerator of a rational polytope can be computed in polynomial time. The distinction here is that we get a simple formula, which happens to be polynomial–time computable.

In dimensions greater than 2, things get more complicated. We can still get formulas through the methods introduced here; however, even the existence of (possible) three–term reciprocity laws for functions appearing in the lattice point count does not guarantee polynomial–time computability. The details will be described in a forthcoming paper \[BDR\].

## 5 Reciprocity laws

As another remark, we can recover the reciprocity law for the classical Dedekind sum (\[De\], Chapter 2 of \[RG\]) from our formulas:

###### Corollary 5.1 (Dedekind)

$$S(a,b;0,0)+S(b,a;0,0)=\frac{1}{4}+\frac{1}{12}\left(\frac{a}{b}+\frac{1}{ab}+\frac{b}{a}\right).$$

Proof. It is well known \[E\] that the constant term in the Ehrhart polynomial, the integer–point enumeration function of a lattice polytope (that is, a polytope with integral vertices) equals the Euler characteristic of the polytope. Consider the simplest case of our triangle mentioned in Proposition 3.5. If we dilate this polytope by $`t=pqw`$, that is, only by multiples of $`pq`$, we obtain the dilates of a lattice polytope $`𝒫`$. Proposition 3.5 simplifies for these $`t`$ to

$`L(\overline{𝒫},w)={\displaystyle \frac{pqw^2}{2}}+{\displaystyle \frac{w}{2}}\left(p+q+1\right)+{\displaystyle \frac{1}{4}}+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{pq}}\right)\sigma (q,p,0)\sigma (p,q,0)+1.`$
On the other hand, we know that the constant term is the Euler characteristic of $`𝒫`$ and hence equals 1, which yields the identity

$$\frac{1}{4}+\frac{1}{12}\left(\frac{p}{q}+\frac{q}{p}+\frac{1}{pq}\right)\sigma (q,p,0)\sigma (p,q,0)=0.$$

The statement follows now by rewriting the Dedekind sums in terms of the original definition via (15). $`\mathrm{}`$

As a concluding consequence of our formulas, we rederive a reciprocity law due to Gessel \[G\], interpreting it at the same time geometrically.

###### Corollary 5.2 (Gessel)

Let $`p`$ and $`q`$ be relatively prime and suppose that $`t`$ is an integer such that $`1tp+q`$. Then

$`{\displaystyle \frac{1}{p}}{\displaystyle \underset{\lambda ^p=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^q\right)\left(1\lambda \right)}}+{\displaystyle \frac{1}{q}}{\displaystyle \underset{\lambda ^q=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^p\right)\left(1\lambda \right)}}`$
$`={\displaystyle \frac{t^2}{2pq}}+{\displaystyle \frac{t}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right){\displaystyle \frac{1}{4}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+1\right){\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{1}{pq}}+{\displaystyle \frac{q}{p}}\right).`$
It is easy to see that the reciprocity law for classical Dedekind sums (Corollary 5.1) is a special case of Gessel’s theorem. Before proving Gessel’s theorem below, we find it useful to have the lattice point count operator for the interior of our polytope. The following central theorem, conjectured by Ehrhart \[E\] and first proved by Macdonald \[Ma\], enables us to do this:

###### Theorem 5.3 (Ehrhart–Macdonald Reciprocity Law)

If a rational polytope $`𝒫`$ is homeomorphic to a $`d`$–sphere then

$$L(𝒫^{},t)=(1)^dL(\overline{𝒫},t).$$

$`\mathrm{}`$

Note that this theorem allows us to conclude a computability statement for the lattice point count in the interior of a two–dimensional rational polytope similar to Theorem 4.1. Using Theorem 5.3 we get from Proposition 2.1 the

###### Corollary 5.4

For the rectangular rational triangle $`𝒯`$ given by (2) with $`a=b=0`$, $`c=r=1`$, and $`p`$ and $`q`$ relatively prime,

$`L(𝒯^{},t)={\displaystyle \frac{t^2}{2pq}}{\displaystyle \frac{t}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right)+{\displaystyle \frac{1}{4}}\left(1+{\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}\right)+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{pq}}\right)`$
$`+{\displaystyle \frac{1}{p}}{\displaystyle \underset{\lambda ^p=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^q\right)\left(1\lambda \right)}}+{\displaystyle \frac{1}{q}}{\displaystyle \underset{\lambda ^q=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^p\right)\left(1\lambda \right)}}.`$
$`\mathrm{}`$

Alternatively, we could have derived Corollary 5.4 from scratch in a similar way as Proposition 2.1.

Proof of Corollary 5.2. Consider dilates of the triangle given in Corollary 5.4, that is,

$$t𝒯^{}=\{(x,y)^2:x,y>0,px+qy<t\}.$$

By the very definition, $`t𝒯^{}`$ does not contain any integer points for $`1tp+q`$, in other words, $`L(𝒯^{},t)=0`$. Hence Corollary 5.4 yields an identity for these values of $`t`$:

$`0={\displaystyle \frac{t^2}{2pq}}{\displaystyle \frac{t}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right)+{\displaystyle \frac{1}{4}}\left(1+{\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}\right)+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{q}{p}}+{\displaystyle \frac{1}{pq}}\right)`$
$`+{\displaystyle \frac{1}{p}}{\displaystyle \underset{\lambda ^p=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^q\right)\left(1\lambda \right)}}+{\displaystyle \frac{1}{q}}{\displaystyle \underset{\lambda ^q=1\lambda }{}}{\displaystyle \frac{\lambda ^t}{\left(1\lambda ^p\right)\left(1\lambda \right)}}.`$
We can rephrase Corollary 5.2 in terms of Dedekind–Rademacher sums by means of Corollary 3.4:

###### Corollary 5.5

Let $`p`$ and $`q`$ be relatively prime and suppose that $`t`$ is an integer such that $`1tp+q`$. Then

$`\sigma (q,p,t)+\sigma (p,q,t)\stackrel{\text{def}}{=}{\displaystyle \underset{k=0}{\overset{p1}{}}}\left(\left({\displaystyle \frac{qkt}{p}}\right)\right)\left(\left({\displaystyle \frac{k}{p}}\right)\right)+{\displaystyle \underset{k=0}{\overset{q1}{}}}\left(\left({\displaystyle \frac{pkt}{q}}\right)\right)\left(\left({\displaystyle \frac{k}{q}}\right)\right)`$
$`={\displaystyle \frac{t^2}{2pq}}{\displaystyle \frac{t}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right)+{\displaystyle \frac{1}{4}}+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{1}{pq}}+{\displaystyle \frac{q}{p}}\right)\left(\left({\displaystyle \frac{t}{p}}\right)\right)\left(\left({\displaystyle \frac{t}{q}}\right)\right).`$
$`\mathrm{}`$

This version of Gessel’s reciprocity law bears something surprising: its form is essentially identical to Knuth’s version \[K\] of Rademacher’s reciprocity law for the Dedekind–Rademacher sums, with two differences: Gessel’s theorem requires $`t`$ to be an integer, whereas $`t`$ in Knuth’s reciprocity law. On the other hand, the conditions in Knuth’s theorem are $`p<q`$ and $`0tq`$, which suffices for all practical purposes, however, Gessel’s range on $`t`$ is bigger. In fact, is not hard to remove the integrality condition on $`t`$, which unifies Knuth’s and Gessel’s reciprocity theorem:

###### Theorem 5.6

Let $`p`$ and $`q`$ be relatively prime and suppose that $`t`$ is a real number such that $`1tp+q`$. Then

$`\sigma (q,p,t)+\sigma (p,q,t)={\displaystyle \frac{[t]^2}{2pq}}+{\displaystyle \frac{[t]}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}+{\displaystyle \frac{1}{pq}}\right)+{\displaystyle \frac{1}{4}}+{\displaystyle \frac{1}{12}}\left({\displaystyle \frac{p}{q}}+{\displaystyle \frac{1}{pq}}+{\displaystyle \frac{q}{p}}\right)`$
$`\left(\left({\displaystyle \frac{[t]}{p}}\right)\right)\left(\left({\displaystyle \frac{[t]}{q}}\right)\right){\displaystyle \frac{((t))}{2}}\left({\displaystyle \frac{1}{p}}+{\displaystyle \frac{1}{q}}\right){\displaystyle \frac{1}{4p}}{\displaystyle \frac{1}{4q}}.`$
Proof. We will denote the fractional part of $`x`$ by $`\{x\}=x[x]`$. Let $`t=n+r`$, where $`n`$ and $`r,0r<1`$ (so $`r=\{t\}`$), then

$`\sigma (a,b,t)={\displaystyle \underset{k=0}{\overset{b1}{}}}\left(\left({\displaystyle \frac{k}{b}}\right)\right)\left(\left\{{\displaystyle \frac{ka+n+r}{b}}\right\}{\displaystyle \frac{1}{2}}\right)={\displaystyle \underset{k=0}{\overset{b1}{}}}\left(\left({\displaystyle \frac{k}{b}}\right)\right)\left(\left\{{\displaystyle \frac{ka+n}{b}}\right\}+{\displaystyle \frac{r}{b}}{\displaystyle \frac{1}{2}}\right)`$
$`={\displaystyle \underset{k=0}{\overset{b1}{}}}\left(\left({\displaystyle \frac{k}{b}}\right)\right)\left(\left({\displaystyle \frac{ka+n}{b}}\right)\right)+{\displaystyle \frac{r}{b}}{\displaystyle \underset{k=0}{\overset{b1}{}}}\left(\left({\displaystyle \frac{k}{b}}\right)\right)\stackrel{(\text{10})}{=}\sigma (a,b,n){\displaystyle \frac{r}{2b}}.`$
Hence

$$\sigma (a,b,t)=\sigma (a,b,[t])\frac{\{t\}}{2b}=\sigma (a,b,[t])\frac{1}{2b}((t))\frac{1}{4b}.$$

Now we can use Corollary 5.5 for $`\sigma (a,b,[t])`$, and the statement follows. $`\mathrm{}`$

Acknowledgements We thank the referees for insightful comments on the first version of this paper.

Department of Mathematical Sciences
State University of New York
Binghamton, NY 13902–6000
matthias@math.binghamton.edu

Department of Mathematics
Temple University
Philadelphia, PA 19122
srobins@math.temple.edu