\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\def\BE{\begin{equation}}
\def\EE{\end{equation}}
\def\BD{\begin{displaymath}}
\def\ED{\end{displaymath}}
\def\BA{\begin{array}}
\def\EA{\end{array}}
\def\BEA{\begin{eqnarray}}
\def\EEA{\end{eqnarray}}
\def\BI{\bibitem}

\def\Bbb{\mathbb}

\def\N{\Bbb N}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\R{\Bbb R}
\def\C{\Bbb C}
\def\E{\Bbb E}
\def\F{\Bbb F}
\def\H{\Bbb H}


\def\phi{\varphi}
\def\EPS{\varepsilon}

\def\MB{\mbox}
\def\LD{\ldots}
\def\OV{\overline}

\def\DIV{\,|\,}
\def\NDIV{\, \nmid \,}

\def\BQ{``}
\def\EQ{'' }
\def\EQP{''}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Petersson-Knopp Identity 
\\
\vskip .1in
and Farey Points
}
\vskip 1cm
\large
Kurt Girstmair\\
Institut f\"ur Mathematik \\
Universit\"at Innsbruck\\
Technikerstr.~13/7\\
A-6020 Innsbruck\\
Austria\\
\href{mailto:Kurt.Girstmair@uibk.ac.at}{\tt Kurt.Girstmair@uibk.ac.at} \\
\end{center}

\vskip .2 in

\begin{abstract}
We study Dedekind sums $S(a,b)$ for arguments $a$ near Farey points of the interval $[0,b]$. The Petersson-Knopp identity connects each of these De\-de\-kind sums with a set of other De\-de\-kind sums.
In the case considered here, this identity has a very specific interpretation,
inasmuch as each De\-de\-kind sum occurring in this identity is close to a certain expected value. Conversely, each of these expected values occurs with a certain frequency,
a frequency that is consistent with the Petersson-Knopp identity.
\end{abstract}

\section{Introduction and results}
\label{s1}

Let $b$ be a positive integer and $a\in \Z$. The classical {\em De\-de\-kind sum} $s(a,b)$ is defined by
\BD
   s(a,b)=\sum_{k=1}^b ((k/b))((ak/b))
\ED
where $((\LD))$ is the \BQ sawtooth function\EQP, defined by
\BD
\label{1.1}
  ((t))=\begin{cases}
                 t-\lfloor t\rfloor-1/2, & \text{ if  $t\in\R\smallsetminus \Z$;} \\
                 0, & \text{ if  $t\in \Z$;}
               \end{cases}
\ED
see, for instance, \cite{RaWh}. In many cases it is more
convenient to work with
\BD
 S(a,b)=12s(a,b)
\ED instead.
We call $S(a,b)$ a {\em normalized} De\-de\-kind sum. In addition, we say that $S(a,b)$ is a {\em primitive} De\-de\-kind sum
if $\gcd(a,b)=1$. In the opposite case $S(a,b)$ is called {\em imprimitive}. Note that
\BD
 S(ad,bd)=S(a,b)
\ED
for every positive integer $d$; see \cite[Th.\ 1]{RaWh}. Therefore, each imprimitive De\-de\-kind sum  $S(a,b)$ is equal to the primitive
De\-de\-kind sum $S(a/d,b/d)$, where $d=\gcd(a,b)$. We also note the periodicity
\BE
\label{1.1.0}
   S(a+b,b)=S(a,b)
\EE
of (not necessarily primitive) De\-de\-kind sums.

Let us start with a special case of what we are going to do in the sequel. Let $a<b$ be positive integers, $\gcd(a,b)=1$, and $p$ a prime not dividing $a, b$.
Then the normalized De\-de\-kind sums
\BE
\label{1.1.1}
 S(pa,b)\: \MB{ and }\: S(a+jb,pb),\: j\in\{0,\LD,p-1\},
\EE
are primitive with one exception. Indeed, if $a+jb\equiv 0$ (mod $p$), then $S(a+jb,pb)=S((a+jb)/p,b)$. Suppose we know that all De\-de\-kind sums (\ref{1.1.1}) are
positive. Then we also know that $S(a,b)$ is positive. Moreover, we know that at least one of the De\-de\-kind sums (\ref{1.1.1})
is $\geq S(a,b)$, whereas the sum of any $p$ of them must be $<(p+1)S(a,b)$. This is an immediate consequence of the Petersson-Knopp identity, which, in this
special case, reads
\BD
  S(pa,b)+\sum_{j=0}^{p-1}S(a+jb,pb)=(p+1)S(a,b).
\ED
In what follows we discuss a situation where we know much more, namely, that one of the De\-de\-kind sums (\ref{1.1.1}) is close to $pS(a,b)$, whereas each of the $p$ remaining ones is
close to $S(a,b)/p$. Hence the Petersson-Knopp identity has a very specific interpretation in this context.


In two previous papers \cite{Gi1,Gi2} we studied the behavior of primitive De\-de\-kind sums near {Farey points}. We briefly recall the
necessary notation. Let the positive integer $b$ be given and assume $b\geq 4$. For a positive integer $d$, $d<b^{1/4}$, let $c\in\Z$, $\gcd(c,d)=1$.
Then $c/d$ is a Farey fraction of an order $<b^{1/4}$ in the usual sense; see \cite[p. 125]{Hu}.
We say that $b\cdot c/d$ is a {\em Farey point with respect to} $b$.
Put
\BE
\label{1.2}
  \alpha=\sqrt{b/d^3}.
\EE
We consider the interval
\BD
\label{1.3}
   \{x\in\R: |x-b\cdot c/d|\leq \alpha-1\}
\ED
around the Farey point $b\cdot c/d$.
Let $a$ be an integer, $\gcd(a,b)=1$, inside this interval. Then the primitive De\-de\-kind sum $S(a,b)$
satisfies
\BD
  S(a,b)\begin{cases}<0,& \text{ if }a<b\cdot c/d;\\
                    >0, & \text{ if } a>b\cdot c/d;
        \end{cases}
\ED
see \cite[Th. 1 and formula (5)]{Gi1}.
In order to avoid tedious distinctions, we restrict ourselves to integers $a$ in the {\em right} half of this interval, so $S(a,b)>0$. The whole theory remains
valid for integers in the left half, but with $S(a,b)$ negative.

Hence we say that $a\in\Z$, $\gcd(a,b)=1$, is a {\em neighbor} of the Farey point $b\cdot c/d$ if
\BE
\label{1.3.1}
0\leq a-b\cdot c/d\leq \alpha-1.
\EE
Note that $a-b\cdot c/d\ne 0$ since $a/b=c/d$ is impossible (both fractions are reduced, and $0<d<b$).
For such a neighbor $a$, $S(a,b)$ is not only positive, but its value is,
as a rule, close to an expected value, which can be defined as follows. Put
\BE
\label{1.4}
  q=ad-bc.
\EE
Then $q>0$ since $q/d=a-b\cdot c/d>0$. Now the {\em expected value} of $S(a,b)$
is
\BE
\label{1.5}
 E(a,b)= \frac b{dq}
\EE
(which is $>0$).

Of course, this definition requires some justification.
To this end we consider the three-term relation for De\-de\-kind sums
\BE
\label{3.1}
 S(a,b)=\frac b{dq}+S(c,d)+S(t,q)+\frac d{bq}+\frac q{db}-3;
\EE
see \cite[Lemma 3]{Gi1}. Here $q$ is defined by (\ref{1.4}) and $t$ is an integer defined by $a,b,c,d$. The exact value of $t$ is not of interest for our purpose. First we observe
$d<b$ and, by (\ref{1.3.1}) and (\ref{1.4}), $q<\sqrt{b/d}<b$. We have, thus,
\BD
  0<\frac d{bq}+\frac q{db}<2.
\ED
Next we note
\BE
\label{3.3}
  |S(c,d)|<d\: \MB{ and }\: |S(t,q)|<q;
\EE
see \cite[Satz 2]{Ra}. Hence $S(a,b)$ is close to $E(a,b)=b/(dq)$ whenever $d$ and $q$ are small. For instance, we may assume
$a-b\cdot c/d\leq b^{1/12}$ for a sufficiently large number $b$. Then $q\leq b^{1/12}b^{1/4}=b^{1/3}$, but $b/(dq)\geq b^{5/12}$. Because $b^{1/3}$ is small relative to $b^{5/12}$,
$S(a,b)$ is close to $E(a,b)$.

In most cases, however, $S(a,b)$ is close to $E(a,b)$ even if $a$ is only a {\em neighbor} of $b\cdot c/d$ in the above sense, since $|S(c,d)|$ is much smaller than $d$ and $|S(t,q)|$ much smaller than $q$.
Indeed, it is reasonable to expect $|S(c,d)|\leq 5\log d$ and $|S(t,q)|\leq 5\log q$, say.
This is due to the main result of the paper \cite{Va}, which allows to determine the asymptotic proportion of pairs $(c,d)$, $0\leq c<d\leq N$, $\gcd(c,d)=1$, such that
$|S(c,d)|<C\log d$ for a given constant $C>0$, as $N$ tends to infinity. For $C=5$ this proportion is about $76.8$\% , and for $C=10$ about $88.0$\%.


Another argument in favor of small values of $|S(c,d)|$ and $|S(t,q)|$ is the {\em mean value} of all numbers $|S(c,d)|$, $0\leq c<d$, $\gcd(c,d)=1$, for a given
positive integer $d$. As $d$ tends to infinity, this mean value is $\leq \log^2d\cdot 6/\pi^2+O(\log d)$; see \cite{GiSch}.



The Petersson-Knopp identity is a relation between $S(a,b)$ and certain other De\-de\-kind sums; see \cite{Pa}. Indeed, if $n$ is a natural number,
then
\BE
\label{1.7}
   \sum_{r\DIV n}\sum_{j=0}^{r-1} S\left(\frac nr a+jb,rb\right)=\sigma(n)S(a,b).
\EE
Here $r$ runs through the (positive) divisors of $n$ and $\sigma(n)=\sum_{r\DIV n}r$ is the sum of the divisors of $n$.

The De\-de\-kind sums in (\ref{1.7}) are not necessarily primitive. In order to apply results about neighbors of Farey points, we need primitive De\-de\-kind sums, however.
In view of the periodicity (\ref{1.1.0}), it suffices to restrict $c$ to the range
$0\leq c<d$, $\gcd(c,d)=1$. Let $a$ be a neighbor of $b\cdot c/d$. For $r\DIV n$ and $j\in\{0,\LD,r-1\}$ put
\BD
\label{1.9}
  k(r,j)=\left(\frac nr a+jb, rb\right) \: \MB{ and }\: m(r,j)=\left(\frac nr c+jd,rd\right).
\ED
So both $k(r,j)$ and $m(r,j)$ are positive integers.
Moreover, put
\begin{eqnarray*}
\label{1.11}
  a(r,j)=\frac{\frac nr a+jb}{k(r,j)},\quad b(r,j)=\frac{rb}{k(r,j)},\\
  c(r,j)=\frac{\frac nr c+jd}{m(r,j)},\quad d(r,j)=\frac{rd}{m(r,j)}.
\end{eqnarray*}
In the sequel we simply write
\BD
S'(r,j)=S(a(r,j),b(r,j))=S\left(\frac nra+jb,rb\right)
\ED
and
\BD
 E'(r,j)=E(a(r,j), b(r,j)).
\ED
Then we have the following result.

\begin{theorem}
\label{t1}
In the above setting, let $0\leq c<d$, $\gcd(c,d)=1$, $\alpha\geq n^{3/2}+n$ and
\BD
  0<a-b\cdot c/d\leq\alpha/n-1.
\ED
For each pair $(r,j)$, $r\DIV n$, $j\in\{0,\LD,r-1\}$, the number $a(r,j)$ is a neighbor of the Farey point $b(r,j)\cdot c(r,j)/d(r,j)$ of the interval $[0, b(r,j)]$. Hence
$S'(r,j)$ is positive. Its expected value is
\BE
\label{1.13}
        E'(r,j)=\frac{m(r,j)^2}n \cdot E(a,b),
\EE
where $E(a,b)$ is the expected value of $S(a,b)$, see {\rm(\ref{1.5})}.
\end{theorem}


In view of the Petersson-Knopp identity (\ref{1.7}), one expects that
\BE
\label{1.14}
  \sum_{r\DIV n}\sum_{j=0}^{r-1}E'(r,j)=\sigma(n)E(a,b).
\EE
This is true, but we have a much more precise result about the expected values $E'(r,j)$. Indeed, they follow
a very regular pattern.

\begin{theorem}
\label{t2}
In the above setting, the numbers $m(r,j)$ divide $n$. Conversely, for every positive divisor $m$ of $n$,
\BE
\label{1.15}
  \#\left\{(r,j): r\DIV n, j\in\{0,\LD,r-1\}, E'(r,j)=\frac{m^2}n E(a,b)\right\}=\frac nm.
\EE
\end{theorem}



By (\ref{1.13}) and (\ref{1.15}), the left hand side of (\ref{1.14}) reads
\BD
 \sum_{m\DIV n} \frac nm\cdot\frac{m^2}nE(a,b),
\ED
which obviously equals $\sigma(n)\cdot E(a,b)$.



\begin{example} Let $n=12$. In this case there are $\sigma(12)=28$ De\-de\-kind sums $S'(r,j)$.
The corresponding values of $E'(r,j)/E(a,b)$ are $1/12$, $1/3$, $3/4$, $4/3$, $3$, $12$, respectively.
Let $d=9$ and $c=1$.
We chose $b$ so large that $\alpha/n-1\geq 10$. This means $b\geq 12702096$. Then it is obvious that
$\alpha\geq 132\geq n^{3/2}+n\approx 53.569$. We used a random generator to produce a number $b$, $1.28\cdot 10^7<b<10^8$. It gave us
$b=31537789$. The Farey point $b\cdot c/d$ is approximately $3504198.78$. Since $\alpha/n-1\approx 16.33$, we can choose $a=3504214$,
which is prime to $b$, and $a-b\cdot c/d\approx 15.22$.  Then $S(a,b)\approx 25537.432$ and $E(a,b)\approx 25578.093$. We computed the
relative deviation
\BE
\label{1.17}
  \left|\frac{S'(r,j)}{E'(r,j)}-1\right|
\EE
of each of the said 28 De\-de\-kind sums from its expected value. It turns out that the largest relative deviation is $\approx 0.04659$ or nearly $4.7$\%.
It occurs for $r=6$, $j=1$, where $E'(r,j)=(1/12)E(a,b)$. The mean relative deviation, i.e., the arithmetic mean of all values (\ref{1.17}),
is $\approx 0.0060$ or $0.6$\%. Further empirical results can be found in Section \ref{s3}.
\end{example}

\begin{remark} The example shows that there are, compared with the size of $b$, only few integers $a$ such that $0<a-b\cdot c/d\leq \alpha/n-1$
for a fixed value of $d$ and $0\leq c<d$, $\gcd(c,d)=1$. In the case of the example their number amounts to $\approx 6\cdot 15=90$.
However, one should be aware of the fact that
each number $a$ of this kind also satisfies $a-b\cdot c/d\leq\alpha/n'-1$ for all integers $n'$, $1\leq n'<n$. Therefore, if $\gcd(a,b)=1$,
the number $a$ gives rise not only to the $\sigma(n)$ De\-de\-kind sums $S'(r,j)$ for $n$,
but also to $\sigma(n')$ analogous De\-de\-kind sums for each positive integer $n'<n$ (the case $n'=1$ includes $S(a,b)$).
For $n=12$ their totality amounts to $\sigma(1)+\sigma(2)+\cdots+\sigma(12)=112$.
In general,
\BD
  \sum_{n'=1}^n\sigma(n') = \frac{\pi^2}{12}n^2+O(n\log n);
\ED
see \cite[p.\ 113]{Hu}.
Hence there is quite a number of De\-de\-kind sums whose expected values are known.

\end{remark}

\section{Proofs}
\label{s2}

Suppose that the assumptions of Theorem \ref{t1} hold. In particular, let $r$ divide $n$ and $j\in\{0,\LD,r-1\}$.

We first show that $m(r,j)$ divides $n$. Let $p$ be a prime. We use the {\em $p$-exponent} $v_p(t)$ of an integer $t\ne 0$,
which is given by $t=p^{v_p(t)}t'$, $\gcd(p,t')=1$. We show that $v_p(m(r,j))\leq v_p(n)$ for all primes $p$. To this end
recall that $m(r,j)=\gcd(\frac nr c+jd, rd)$.
First suppose $p\NDIV d$. Then $v_p(m(r,j))\leq v_p(r)\leq v_p(n)$. Next let $p\DIV d$, so $v_p(d)=s\geq 1$.
Since $\gcd(c,d)=1$, $v_p(c)=0$ and $v_p(\frac nr c)=v_p(\frac nr)$. If $v_p(\frac nr)<s$, then $v_p(\frac nrc+jd)=v_p(\frac nr)\leq v_p(n)$. If $v_p(\frac nr)\geq s$,
then $v_p(n)\geq v_p(r)+s$. In this case $v_p(rd)=v_p(r)+s\leq v_p(n)$, and $v_p(m(r,j))\leq v_p(rd)\leq v_p(n)$.

The same arguments work for $k(r,j)=(\frac nr a+jb, rb)$ and $a,b$ instead of $c,d$. They show that $k(r,j)$ divides $n$.


\begin{proof}[Proof of Theorem \ref{t1}] In order to simplify the notation for the purpose of this proof,
we write $a'=a(r,j)$, $b'=b(r,j)$, $c'=c(r,j)$, $d'=d(r,j), k'=k(r,j)$, and $m'=m(r,j)$.
First we observe $b'\geq b/k'\geq b/n$, and since $\alpha\geq 2n$, we have $b'\geq 4$.

Next we consider
\BE
\label{2.1}
  q'=a'd'-b'c'.
\EE
A short calculation shows
\BE
\label{2.3}
 q'=\frac n{k'm'}\,q,
\EE
where $q=ad-bc$; see (\ref{1.4}).
Now $a'$ is a neighbor of $b'\cdot c'/d'$,
if $0<a'-b'\cdot c'/d' \leq\sqrt{b'/d'^3}-1$, i.e.,
\BD
  0<q'\leq \sqrt{{b'}/{d'}}-d';
\ED
see (\ref{1.3.1}). Here $q'>0$ follows from (\ref{2.3}), since $q>0$. Because $\sqrt{b'/d'}=\sqrt{m'/k'}\cdot\sqrt{b/d}$, $a'$ is a neighbor of $b'\cdot c'/d'$, if
\BD
   \frac n{k'm'}\,q\leq \sqrt{\frac{m'}{k'}}\cdot\sqrt{\frac bd}-\frac{rd}{m'},
\ED
by (\ref{2.3}). This condition can be written as
\BE
\label{2.5}
  a-b\cdot\frac cd= \frac qd\leq \frac{k'^{1/2}m'^{3/2}}n\cdot\alpha-\frac{rk'}n.
\EE
Let $\rho$ be the right hand side of (\ref{2.5}), i.e.,
\BD
 \rho=\frac{k'^{1/2}m'^{3/2}}n\cdot\alpha-\frac{rk'}n.
\ED
If $k'=m'=1$ and $r=n$, then $\rho$ becomes $\alpha/n-1$.
We show that $\rho$ is always $\geq \alpha/n-1$, provided that $\alpha\geq n^{3/2}+n$. In this case the condition
$q/d\leq \alpha/n-1$ implies that $a'$ is a neighbor of $b'\cdot c'/d'$ for {\em all} $r,j$ in question.

In the case $k'=1$ we have $rk'/n\leq r/n\leq 1$ and $\rho\geq \alpha/n-1$.
Hence assume $k'>1$. Since $\rho$ is $\geq k'^{1/2}\alpha/n-rk'/n$, $\rho<\alpha/n-1$ implies
$k'^{1/2}\alpha-rk'/n<\alpha/n-1$. Because $k'^{1/2}>1$, this inequality can be written as
$\alpha<(rk'-n)/(k'^{1/2}-1)$. Since $r\leq n$, it implies $\alpha<n(k'^{1/2}+1)$. We know that $k'$ divides $n$,
hence we obtain $\alpha<n^{3/2}+n$ as a necessary condition for $\rho<\alpha/n-1$.

Finally, we compute
\BD
  E(a',b')=\frac{b'}{d'q'}=\frac{rb/k'}{rd/m'\cdot q\cdot n/(k'm')}=\frac{m'^2}n\, \frac b{dq}=\frac{m'^2}nE(a,b).
\ED
\end{proof}

In the sequel we need the following notation. For positive integers $r$ and $d$ let $(r)_d$ and $(r)_d^{\bot}$ denote the {\em $d$-part} and the {\em $d$-free part} of $r$, respectively, i.e.,
\BD
   (r)_d=\prod_{p\DIV r,\, p\DIV d} p^{v_p(r)}\MB{ and }(r)_d^{\bot}=\prod_{p\DIV r,\, p\NDIV d} p^{v_p(r)},
\ED
where $v_p(r)$ is defined as above.
The proof of Theorem \ref{t2} is more complicated than that of Theorem \ref{t1} and is based on the following lemmas.

\begin{lemma}
\label{l1}
Let $r,d$ be positive integers and $s\in\Z$ such that $\gcd(s,d)=1$.
Then
\BD
  \#\{\OV k\in\Z/r\Z: \OV{s+kd}\in (\Z/r\Z)^{\times}\}=(r)_d\,\phi((r)_d^{\bot}),
\ED
where $\phi$ denotes Euler's totient function.
\end{lemma}


\begin{proof} We use the Chinese remainder theorem to decompose $\Z/r\Z$ into its $p$-parts $\Z/p^{e_p}\Z$, where $e_p=v_p(r)\geq 1$.

\bigskip

\noindent Case 1: $p\DIV d$. Then for all $k\in \Z$ we have $s+kd\equiv s\not\equiv 0$ (mod $p$), i.e.,
$\OV{s+kd}\in(\Z/p^{e_p}\Z)^{\times}$. Hence
\BD
  \#\{\OV k\in\Z/p^{e_p}\Z: \OV{s+kd}\in(\Z/p^{e_p}\Z)^{\times}\}=p^{e_p}.
\ED

\bigskip

\noindent Case 2: $p\NDIV d$. Let $k\in\Z$. Let $d^*$ be an inverse of $d$ (mod $p$). Then $s+kd\not\equiv 0$ (mod $p$) if, and only if, $k\not\equiv -sd^*$ (mod $p$). Therefore,
\BD
  \#\{\OV k\in\Z/p^{e_p}\Z: \OV{s+kd}\in(\Z/p^{e_p}\Z)^{\times}\}=p^{e_p}(1-1/p)=\phi(p^{e_p}).
\ED
\end{proof}

\begin{lemma}
\label{l2}
Let $n$ be a positive integer and $m>0$ a divisor of $n$. Let $c,d\in\Z$, $0\leq c<d$, $\gcd(c,d)=1$, and $\delta=\gcd(m,d)$.
Put $n'=n/\delta$, $m'=m/\delta$ and $d'=d/\delta$. Then
\BEA
\label{2.7}
  &&\#\left\{(r,j): r\DIV n,0\leq j\leq r-1, m=\gcd\left(\frac nr c+jd,rd\right)\right\}= \nonumber\\
  &&\sum_{\genfrac{}{}{0pt}{1}{m'\DIV r\DIV n'}{\gcd(n/r,d)=\delta}}(r/m')_{d'}\,\phi((r/m')_{d'}^{\bot}).
\EEA
\end{lemma}


\begin{proof} For given positive divisors $m, r$ of $n$ we determine
\BE
\label{2.9}
  \#\left\{j:0\leq j\leq r-1, m=\gcd\left(\frac nr c+jd,rd\right)\right\}.
\EE
First we show that (\ref{2.9}) equals $0$ if $\gcd(n/r,d)\ne\delta$. To this end suppose that $m=\gcd(\frac nr c+jd,rd)$ for some $j$.
Since $\delta\DIV m$, we have $\delta\DIV \frac nr c+jd$, and because $\delta\DIV d$, we obtain $\delta\DIV \frac nrc$.
But $\gcd(c,d)=1$, and so $\delta\DIV \frac nr$. Put $d_r=\gcd(\frac nr,d)$. We have seen $\delta\DIV d_r$. Conversely, $d_r$ divides
both $\frac nr c+jd$ and $rd$, whence $d_r\DIV m$. But $d_r\DIV d$, which implies $d_r\DIV \gcd(m,d)=\delta$. Altogether, $d_r=\delta$.
This means that $m=\gcd(\frac nr c+jd,rd)$ can hold only if $d_r=\delta$.

Therefore, we can restrict our investigation of (\ref{2.9}) to those $r$ for which $\gcd(\frac nr,d)=\delta$. As above,
put $d'=d/\delta$ and $n'=n/\delta$. Since $\delta\DIV n/r$, $r$ divides $n'$. Suppose that $m=\gcd(\frac nr c+jd,rd)$. Then
$ m=\delta m' \MB{ with } m'=\gcd(\frac{n'}r c+jd',rd')$.
Because $\gcd(\frac nr,d)=\delta$, we have $\gcd(\frac{n'}r,d')=1$ and $\gcd(\frac{n'}r c+jd',d')=1$. Accordingly,
\BE
\label{2.11}
   m'=\gcd\left(\frac{n'}r c+jd',r\right).
\EE
Conversely, suppose that $m'=m/\delta$ divides $r$. Since $\gcd(m',d')=1$, there is a number $j_0\in\{0,\LD,m'-1\}$ such that
$\frac{n'}r c+j_0d'\equiv 0$ (mod $m'$). If $m'$ has the form (\ref{2.11}) for a number $j\in\{0,\LD,r-1\}$, then $j\equiv j_0$ (mod $m'$), and so
$ j=j_0+km'$ for a uniquely determined $k\in\{0,\LD, r/{m'}-1\}$. For such a number $j$, we have
\BD
 \left(\frac{n'}r c+jd'\right)/{m'}=s+kd'
\ED
with $s=(\frac{n'}r c+j_0d')/m'$. Now (\ref{2.11}) holds if, and only if,
\BD
  \gcd(s+kd',r/{m'})=1.
\ED
Therefore, we have to count the $\OV k\in\Z/\frac r{m'}\Z$ such that $\OV{s+kd'}\in(\Z/\frac r{m'}\Z)^{\times}$. From Lemma \ref{l1}
we know that the number of these elements $\OV k$ equals
\BE
\label{2.13}
  \left(r/{m'}\right)_{d'}\,\phi\left(\left(r/{m'}\right)_{d'}^{\bot}\right).
\EE
This number equals that of (\ref{2.9}). We have to sum up the numbers (\ref{2.13}), observing that $\gcd(n/r,d)=\delta$. This yields
(\ref{2.7}).
\end{proof}


For positive integers $n, m$, $m\DIV n$, let $A(m,n)$ denote the number of (\ref{2.7}), i.e.,
\BD
  A(m,n)=\#\left\{(r,j): r\DIV n,0\leq j\leq r-1, m=\gcd\left(\frac nr c+jd,rd\right)\right\}.
\ED

\begin{lemma}
\label{l3}
Let $n,m$ be positive integers, $m\DIV n$, and suppose $n=n_1n_2$ for positive integers $n_1$, $n_2$ such that $\gcd(n_1,n_2)=1$.
Put $m_1=\gcd(m,n_1)$ and $m_2=\gcd(m,n_2)$. Then
\BD
\label{2.15}
  A(m,n)=A(m_1,n_1)A(m_2,n_2).
\ED
\end{lemma}


\begin{proof} All entries of the right hand side of (\ref{2.7}) are multiplicative. Indeed, put $\delta_1=\gcd(\delta,n_1)$ and $\delta_2=\gcd(\delta,n_2)$. Then
$\delta=\delta_1\delta_2$. In the same way, $r=r_1r_2$ with $r_1=\gcd(r,n_1)$ and $r_2=\gcd(r,n_2)$. We also have $n'=n_1'n_2'$ with $n_1'=n_1/\delta_1$ and
$n_2'=n_2/\delta_2$. The respective identity holds for $m'$ and $m_1'=m_1/\delta_1$ and $m_2'=m_2/\delta_2$.
Further, $\gcd(n/r,d)=\delta$ if, and only if, $\gcd(n_1/r_1,d)=\delta_1$ and $\gcd(n_2/r_2,d)=\delta_2$. We note
$(r/m')_{d'}=(r_1/m_1')_{d_1'}(r_2/m_2')_{d_2'}$, where $d_1'=d/\delta_1$ and $d_2'=d/\delta_2$. The same identity holds when we apply the $\bot$ to the respective items.
Finally, the function $\phi$ is also multiplicative. In view of all that, we can write the sum over $r$ as the product of two sums over $r_1$ and $r_2$ and obtain the desired
result.
\end{proof}


\begin{proof}[Proof of Theorem \ref{t2}] We have to show that $A(m,n)=n/m$. By Lemma \ref{l3}, it suffices to prove this identity for prime powers $n=p^e$ and $m\DIV n$. Suppose that $m=p^k$,
$k\leq e$, and $(d)_p=p^s$.

\bigskip

\noindent Case 1: $k\geq s$. Then $\delta=p^s$. We have $m'=p^{k-s}$ and $n'=p^{e-s}$. Let $r=p^t$ with $k-s\leq t\leq e-s$. By Lemma \ref{l2},
\BD
  A(m,n)=\sum_{\genfrac{}{}{0pt}{1}{k-s\leq t\leq e-s}{\gcd(p^{e-t},p^s)=p^s}}\phi(p^{t+s-k}),
\ED
since $r/m'=p^{t+s-k}$ and $(d')_p=(d/\delta)_p=1$. Obviously, $\gcd(p^{e-t},p^s)=p^s$ holds for all $t$ in question, because $e-t\geq s$. We obtain
\BD
   A(m,n)=\sum_{u=0}^{e-k}\phi(p^u)=p^{e-k}=n/m.
\ED

\bigskip

\noindent Case 2: $k<s$. Then $\delta=p^k$. Moreover, $m'=1$ and $n'=p^{e-k}$. If $r=p^t$, $0\leq t\leq e-k$, we have
\BD
  \gcd(n/r,d)=\gcd(p^{e-t}, p^s)=\begin{cases} p^{e-t}, & \MB{ if } e-t\leq s,\\
                                               p^s,     & \MB{ if } e-t>s.
                                 \end{cases}
\ED
Since $r$ must satisfy $\gcd(n/r,d)=\delta=p^k$ and $k<s$, only the first case is suitable for our purpose, and, indeed, only for $e-t=k$,
i.e., $t=e-k$. So only the summand for $r=p^{e-k}$ remains. We have $(d')_p=p^{s-k}$ with $s-k\geq 1$. Accordingly,
$(r/m')_{d'}=(r)_{d'}=r=p^{e-k}$ and $A(m,n)=n/m$, again.
\end{proof}





\section{Numerical evidence for the expected values}
\label{s3}




We return to the setting of the Theorems \ref{t1} and \ref{t2}.
Suppose that the size of $d$ is fixed, say $d\leq n$, whereas $b$ may become large.
As in Theorem \ref{t1}, assume $\alpha\geq n^{3/2}+ n$ and $q/d\leq \alpha/n-1$. Accordingly, all De\-de\-kind sums
$S(a(r,j),b(r,j))=S'(r,j)$ are positive for $r\DIV n$, $0\leq j\leq r-1$. The expected value of $S'(r,j)$ equals $E'(r,j)=(m(r,j)^2/n)E(a,b)$. By Theorem \ref{t2},
we know that $m(r,j)$ is a divisor of $n$, and, conversely,
each positive divisor $m$ of $n$ has the form $m=m(r,j)$ for exactly $n/m$ pairs $(r,j)$.

Empirical data shows that the relative deviation (\ref{1.17}) of $S'(r,j)$ from $E'(r,j)$ may be large, in the main, if $m(r,j)=k(r,j)=1$ and $q/d$ is close to $\alpha/n$. In this case $E'(r,j)=(1/n)E(a,b)$.
This empirical observation can be explained as follows.
We have
\BD
  q(r,j)=a(r,j)d(r,j)-b(r,j)c(r,j)=\frac n{k(r,j)m(r,j)}\,q;
\ED
see (\ref{2.1}), (\ref{2.3}). Because $m(r,j)=k(r,j)=1$, we obtain $q(r,j)=nq$.
The influence of $S(c(r,j),d(r,j))$ on $S'(r,j)$ in the sense of (\ref{3.1}) is limited since $|S(c(r,j),d(r,j))|\leq d(r,j)\leq rd\leq n^2$. However, the influence of $S((t(r,j), q(r,j))$ may be significant
if $q(r,j)=nq$ is close to $E'(r,j)=(1/n)E(a,b)=b/(ndq)$, i.e., if $q/d$ is close to $\alpha/n$.

Let $(r,j)$ be of this kind and, in addition, the pair $(r_1,j_1)$ such that $m(r_1,j_1)\geq 2$. Then we have
\BD
  q(r_1,j_1)=\frac n{k(r_1,j_1)m(r_1,j_1)}\,q\leq \frac{n}2\, q=\frac{q(r,j)}2.
\ED
On the other hand $E'(r_1,j_1)\geq (4/n)E(a,b)=4E'(r,j)$. This means
\BD
  \frac{q(r_1,j_1)}{E'(r_1,j_1)}\leq \frac 18 \cdot\frac{q(r,j)}{E'(r,j)},
\ED
which is a much better proportion than $q(r,j)/E'(r,j)$, in particular, in the bad case $q(r,j)\approx E'(r,j)$.

As to empirical data, we performed numerous computations, of which, however, we present only the case $n=12$ and $d=9$. We computed the mean value of the relative
deviation (\ref{1.17}) both for all 28 pairs $(r,j)$, $r\DIV 12$, $j=0,\LD,r-1$, and only for those $(r,j)$ with $m(r,j)=1$ (and expected value $E'(r,j)=(1/12)E(a,b)$). By the above, it is not surprising
that the first mean value is always smaller than the second.

We consider $b=10^8+k$, $1\leq k\leq 10000$, and choose the integer $a$ close to $b\cdot c/d+\alpha/n$. To be precise, $a$ is either $\lfloor b\cdot c/d+\alpha/n\rfloor-1$
or $\lfloor b\cdot c/d+\alpha/n\rfloor-2$. If none of these values of $a$ satisfies $\gcd(a,b)=1$, the number $b$ is ruled out. In this way there always remain $\geq 8000$ pairs $(b,a)$ to be investigated.
The following table lists the percentage of $b$'s such that the first mean value
\BD
   M_1=\frac 1{\sigma(n)}\sum_{r\DIV n}\sum_{j=0}^{r-1}\,\left|\frac{S'(r,j)}{E'(r,j)}-1\right|
\ED
is either $\geq 0.05$ or $<0.01$.
The table also displays the percentage of $b$'s such that the second mean value
\BD
   M_2=\frac 1{n}\sum_{m(r,j)=1}\,\left|\frac{S'(r,j)}{E'(r,j)}-1\right|
\ED
is either $\geq 0.05$ or $<0.01$.



\begin{center}
\begin{tabular}{l||r|r|r|r|r|r}
 c        &  1&  2&  4&  5&  7& 8\\
\hline
$M_1\geq 0.05$& 1.2 \%& 1.3 \%& 1.3 \%& 1.3 \%&1.3 \%&1.3 \% \rule{0mm}{5mm}\\
\hline
$M_1<0.01$& 93.4 \%& 93.7 \%& 93.7 \%& 93.6 \%& 93.8 \%& 92.9 \%\rule{0mm}{5mm}\\
\hline
$M_2\geq 0.05$& 1.9 \%& 2.0 \%& 1.9 \%& 2.0 \%&2.0 \%&2.0 \%\rule{0mm}{5mm}\\
\hline
$M_2<0.01$& 73.6 \%&80.5 \%&78.7 \%&78.8 \%& 80.6 \%& 70.6 \%\rule{0mm}{5mm}\\
\multicolumn{7}{c}{{\bf Table 1:} $n=12$, $d=5$, $b=10^8+k$, $1\leq k\leq 10000$\rule{0mm}{8mm}}
\end{tabular}
\end{center}



We list the same data for numbers $b=10^9+k$, $1\leq k\leq 10000$.


\begin{center}
\begin{tabular}{l||r|r|r|r|r|r}
 c        &  1&  2&  4&  5&  7& 8\\
\hline
$M_1\geq 0.05$& 0.4 \%& 0.4 \%& 0.4 \%& 0.3 \%&0.3 \%&0.4 \%\rule{0mm}{5mm}\\
\hline
$M_1<0.01$& 97.9 \%&98.0 \%&98.0 \%&98.2 \%& 98.2 \%& 97.9 \%\rule{0mm}{5mm}\\
\hline
$M_2\geq 0.05$& 0.6 \%& 0.6 \%& 0.6 \%& 0.5 \%&0.5 \%&0.6 \%\rule{0mm}{5mm}\\
\hline
$M_2<0.01$& 94.4 \%&94.5 \%&94.7 \%&95.2 \%& 95.1 \%& 94.2 \%\rule{0mm}{5mm}\\
\multicolumn{7}{c}{{\bf Table 2:} $n=12$, $d=5$, $b=10^9+k$, $1\leq k\leq 10000$\rule{0mm}{8mm}}
\end{tabular}
\end{center}

We obtain similar results when we use (pseudo-) random numbers $b$ of the same order of magnitude instead of the (more or less) consecutive numbers $b$ of the tables.
The tables suggest that the approximation of $E'(r,j)$ by $S'(r,j)$ becomes better when $b$ increases while $d$ and $n$ are fixed. This observation is supported by further computations.

\begin{thebibliography}{99}


\BI{Gi1} K. Girstmair, Dedekind sums with predictable signs, {\em Acta Arith.} {\bf 83} (1998), 283--294.

\BI{Gi2}  K. Girstmair, Zones of large and small values for Dedekind sums, {\em Acta Arith.} {\bf 109} (2003), 299--308.

\BI{GiSch} K. Girstmair and J. Schoissengeier, On the arithmetic mean of Dedekind sums, {\em Acta Arith.} {\bf 116} (2005), 189--198.

\BI{Hu} L. K. Hua, {\em Introduction to Number Theory}, Springer-Verlag, 1982.

\BI{Pa}  L. A. Parson, Dedekind sums and Hecke operators, {\em  Math. Proc. Cambridge Philos. Soc.} {\bf 88} (1980), 11--14.

\BI{Ra} H. Rademacher, Zur Theorie der Dedekindschen Summen, {\em Math. Z.} {\bf 63} (1956), 445--463.

\BI{RaWh} H. Rademacher and A. Whiteman, Theorems on Dedekind sums, {\em Amer. J. Math.} {\bf 63} (1941), 377--407.

\BI{Va}  I. Vardi, Dedekind sums have a limiting distribution, {\em Internat. Math. Res. Notices} {\bf 1993}, 1--12.


\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11F20.

\noindent \emph{Keywords: } Dedekind sum, Petersson-Knopp identity,
Farey point, expected value of a Dedekind sum.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  February 19 2020;
revised version received  May 17 2020.
Published in {\it Journal of Integer Sequences}, May 17 2020.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}