0}^{k/2-1}\!\!\sawfrac{\pi_n(j)\pm b}{k} \!&=\! 0 \label{e:saw_sum_pi_+b_2}\\[-3.3em]
\end{align}
In particular, when $b=0$, $4\sum_{j=0}^{k/2-1}\!\!\saww{\frac{j}{k}} =1-k/2$.~\IEEEQE
\end{lemma}
\vspace{-0.05in}

Summations of saw-fractions $\saww{j^2/k}$ and floor-fractions $\flr{j^2/k}$ involving squared integers have never been attempted before in the literature. Below we derive an interesting identity for these sums over a complete residue system.

\begin{lemma}[Sum of saw and floor fractions involving squared integers over a complete residue system]\vspace{-0.07in}
\label{lem:saw_sum_j2_over_residue_system}
\begin{align}\\[-3.1em]
  \sum_{j=0}^{k-1}\!\sawfrac{j^2}{k}  &= \left\{
                                           \begin{array}{ll}
                                            \!\!\!-\sqrt{k}+ 3/2, & \hbox{$\log_2{k}$ even;}\vspace{-0.1in} \\
                                            \!\!\!-3\sqrt{k/8}+ 3/2, & \hbox{$\log_2{k}$ odd.}
                                           \end{array}
                                         \right.\label{e:saw_sum_j2}\vspace{-0.2in}\\
    \sum_{j=0}^{k-1}\!\flrfrac{j^2}{k}  &= \left\{
                                           \begin{array}{ll}
                                            \!\!\!\frac{k^2}{3}-k+\frac{3\sqrt{k}}{2}-\frac{4}{3}, &
                                                \hbox{$\log_2{k}$ even;} \vspace{-0.1in}\\
                                            \!\!\!\frac{k^2}{3}-k+\sqrt{2k}-\frac{4}{3}, & \hbox{$\log_2{k}$ odd.}
                                           \end{array}
                                         \right.\label{e:floor_sum_j2}\\[-3.1em]
\end{align}
\end{lemma}
\vspace{-0.05in}

Moreover, for the arithmetic analysis of BRPs $\pi_n$, summations that involve products of saw-fractions of the form $\saww{\!\frac{\vphantom{\pi_n{(j)}}j}{k}\!}\!\!\!\saww{\!\frac{\pi_n{(j)}}{k}\!}$ and their variations are of particular interest.

\begin{lemma}[Sum of products of saw-fractions]\vspace{-0.05in}
\label{lem:prod_saw_fractions}
\begin{align}\\[-3.1em]
        R(k) \triangleq 4k\sum_{j=0}^{k-1}\!\sawfrac{j}{k}\!\!\!\sawfrac{\pi_n{(j)}}{k}
             = \frac{k\log_2(k)}{2} - k + 1 \label{e:R_k_definition}~\IEEEQED\\[-3.1em]
\end{align}
\end{lemma}
\vspace{-0.05in}





More generally, sums of products of the form $\saww{\!\frac{\vphantom{\pi_n(j)}j-b}{k}\!}\!\!\!\saww{\!\frac{\pi_n(j)-c}{k}\!}$ for shift integers $b,c$ can also be evaluated efficiently.\vspace{-0.05in}

\begin{lemma}[Sum of products of saw-fractions with a shift] Let $c^*\!=\!\pi_{\!n\!-\!1}\!\left( (c\!-\!1)/2 \right)$ if $c$ is odd, and $c^*\!=\!\pi_{\!n\!-\!1}\!\left( c/2 \right)$ if $c$ is even.\vspace{-0.25in}
\label{lemma:S_sum}
\begin{align}\\[-3.1em]
\label{e:S_sum}
    S(k,b,c) &\triangleq 4k\sum_{j=0}^{k-1}\!\sawfrac{j-b}{k}\!\!\!\sawfrac{\pi_n(j)-c}{k}
             \!=\! \left\{\!
                  \begin{array}{ll}
                    \!\! 2S(k/2,b,(c-1)/2) + 2k\!\saww{\!\frac{c^*-b}{k}\!} + K_{S}, & \hbox{$c$ odd;} \vspace{-0.05in}\\
                    \!\! 2S(k/2,b,c/2) -2k\!\saww{\!\frac{c^*-b}{k}+\hf\!} + K_{S}, & \hbox{$c$ even.}
                  \end{array}
                \right.\\[-0.2em]
    K_{S} &=   \left\{\!
                        \begin{array}{ll}
                          \!\!\! -2b + k/2 - 1, & \hbox{$0\leq b<k/2$;}\vspace{-0.1in}\\
                          \!\!\! \hphantom{-}2b -3k/2 + 1, & \hbox{$k/2\leq b<k$.}
                        \end{array}
                      \right.\label{w:K_S}\\[-3.1em]
\end{align}
\end{lemma}




Furthermore, we investigate summations that involve products of differences of saw-functions similar to those in~\eqref{eq:INL_saw_formula_K}:\vspace{-0.05in}
\begin{align}
\label{e:T_definition}
T(k,b,c) \triangleq 4k \sum_{j=0}^{k-1}\!\left[\!\sawfrac{j-b}{k}\!\!-\!\!\sawfrac{j}{k}\!\right]
            \!\!\!\left[\!\sawfrac{\pi_{n}(j)-c}{k}\!\!-\!\!\sawfrac{\pi_{n}(j)}{k}\!\right]\\[-3.1em]
\end{align}

\begin{lemma} If $c\!=\!0$ or $\!b=\!0$, then $T(k,b,c)\!=\!0$. Else, let $c^*\!=\!\pi_{\!n\!-\!1}\!\left(\! (c\!-\!1)/2 \!\right)$ if $c$ is odd, $c^*\!=\!\pi_{\!n\!-\!1}\!\left( c/2 \right)$ if $c$ is even. Then\vspace{-0.08in}
\label{lemma:T_sum_minus}
\begin{align}
\label{e:T_sum_minus}\\[-3.0em]
    T(k,b,c) \!=\! \left\{\!
                  \begin{array}{ll}
                    \!\! 2T(k/2,b,(c-1)/2) \!-\! 4b \!-\! k \!\left(\!
                        2\!\flrfrac{c^*-b}{k} \!-\! 2\!\flrfrac{2b}{k} \!-\! \deltafrac{c^*-b}{k}
                        \!+\!\deltafrac{c^*}{k} \!+\! \deltafrac{2b}{k}\!\right), & \hbox{$c$ odd;} \vspace{-0.05in}\\
                    \!\! 2T(k/2,b,c/2) + k\!\left(2\!\flr{\frac{c^*-b}{k}+\hf} \!+\!2\!\flr{\frac{b}{k}\!+\!\hf}
                    \!-\! \delta\!\left(\frac{c^*-b}{k}+\hf\right) \!-\! \delta\!\left(\frac{b}{k}+\hf\right)
                    \!\right), & \hbox{$c$ even.}
                  \end{array}
                \right.\\[-3.2em]
\end{align}
This recursion (and~\eqref{e:S_sum}) can be evaluated using integer arithmetic in at most $n-1$ steps since $T(2,b,c)=0$.~\IEEEQE
\end{lemma}




Note that the recursive solution in~\eqref{e:T_sum_minus} is similar to that for linear permutation polynomials involving Dedekind sums~\cite{2009_Mansour_LCSI}.

Specifically, when $c=\pi_n{(b)}$ in~\eqref{e:T_definition}, a closed form