Prove that two functions are equal only when $s \equiv \pm r^{\pm 1} \pmod{q}$

Question

Let us fix a positive integer $q$, and let us define a functions $P: \mathbb{Z}\times \mathbb{N} \to \mathbb{Z}$ as follows: $$ P(s,t) := \sum_{j=1}^t \left\lfloor \frac{j (s-1) + t}{q} \right\rfloor$$

If we define the function $A_s : \mathbb{N} \to \mathbb{Z}$ by: $$ A_s(t) := P(s,t) + P(-s,t). $$

I claim that $A_s = A_r$ (as functions of $t$) if and only if one of the following is true:

• $s \equiv r \pmod{q}$
• $s \equiv -r \pmod{q}$
• $sr \equiv 1 \pmod{q}$
• $sr \equiv -1 \pmod{q}$.

I do have a proof of both implications, but they are rather involved and a bit too technical. The hardest part is to show that $A_s = A_r$ implies one of the four bullets. I am wondering if this is indeed a hard problem and technical stuff has to play a role in a proof or if I am missing a simpler proof. Even a simple proof of the fact that each of the third and fourth bullets implies $A_s = A_r$ would be nice, since what I have is lengthy and ugly.

Answer 1

Let $\mathcal P_{q,s}$ denote the parallelogram with vertices $(0,\pm\frac{1}{q}), (1,\frac{s}{q}), (-1,-\frac{s}{q})$. The function $$I_{q,s}(t)=2A_s(t)+2\left\lfloor\frac{t}{q}\right\rfloor+2t+1$$ counts the number of lattice points in the dilation $t\cdot\mathcal P_{q,s}$. In fact this is exactly the expression you get by counting the lattice points according to their x-coordinates and then summing everything up.

Now let's apply the map $(x,y)\to (x,sx-qy)$. The parallelogram becomes the square with vertices $(0,\pm1), (\pm1, 0)$ and lattice points are sent to lattice points $(x,y)$ satisfying $y-sx= 0\pmod q$. In this setting symmetry makes it easy to see why $I_{q,s}=I_{q,s'}$ for the four bullet points. In fact, $s'=-s$ corresponds to reflecting everything on the y axis, and $s'=s^{-1}$ corresponds to reflecting everything on the line $x=y$.

---

The converse is much harder and has a really fascinating story to it. First let me mention why people care about this problem. It turns out that this Ehrhart function encodes the multiplicities that $t(t+2), t\in \mathbb N$ appears as an eigenvalue of the Laplace-Beltrami operator on the lens space $L(q,s)$. Knowing that $I(q,s)=I(q,s')$ implies that the two lens spaces $L(q,s)$ and $L(q,s')$ are isospectral (have the same eigenvalues and respective multiplicities).

What is easy to see is that the four bullet points are exactly the conditions which specify lens spaces up to isometry. Of course we have $$\text{isometric} \implies \text{homeomorphic} \implies \text{isospectral}$$ but for 3-dimensional lens spaces it turns out that the opposite implication holds as well. Already the fact that the first arrow is invertible required introducing the notion of Reidemeister torsion. From the above discussion your question is completely equivalent to the statement that isospectral lens spaces in dimension 3 are actually isometric (this is known to be false in higher dimensions). So this is some evidence that the proof will probably have to be a little difficult.

One proof is given in

A. Ikeda, Y. Yamamoto, "On the spectra of 3-dimensional lens spaces", Osaka J. Math. 16(2) (1979), 447-469

for the special case where $q$ is a prime power or twice a prime power. It is proven in full generality in

Y. Yamamoto, "On the number of lattice points in the square |x| + |y| ≤ u with a certain congruence condition", Osaka J. Math. 17(1) (1980), 9–21

The main number theoretic ingredient in Yamomoto's proof is the fact that the numbers $\cot \frac{k\pi}{q}$ for $1\le k\le \frac{q}{2}, \gcd(k,q)=1$ are linearly independent over $\mathbb Q$. If your proof is simpler than Yamamoto's it might be worth publishing for that reason alone.

Answer 2

Here goes a simple proof of the fact that each of the third and fourth bullets implies $A_s=A_r$. This is a basic bijection after all.

We have $$A_s(t)=P(s,t)+P(-s,t)=\sum_{j=1}^t \left(\frac{j(s-1)+t}q+\frac{j(-s-1)+t}q\right)-B_s(t),\\ B_s(t):=\sum_{j=1}^t\left(\left\{\frac{j(s-1)+t}q\right\}+\left\{\frac{j(-s-1)+t}q\right\}\right)$$ (here $\{x\}$ denotes the fractional part of $x$). So we see that $A_s(t)+B_s(t)$ does not depend on $s$, and $A_s(t)=A_r(t)$ is equivalent to $B_s(t)=B_r(t)$.

It is clear that $B_s$ depends only on $s$ modulo $q$ and that $B_s=B_{-s}$. Also $B_s(0)=0$ and for $t>0$ we have $$B_s(t)-B_s(t-1)=\left\{\frac{ts}q\right\}+\left\{\frac{-ts}q\right\} \\+\sum_{j=1}^{t-1}\left(\left\{\frac{j(s-1)+t}q\right\}-\left\{\frac{j(s-1)+t-1}q\right\}\right)\\ +\sum_{j=1}^{t-1}\left(\left\{\frac{j(-s-1)+t}q\right\}-\left\{\frac{j(-s-1)+t-1}q\right\}\right)\\=1-\mathbf{1}\{q|ts\}+2(t-1)\cdot\frac1q\\-\left|j\in \{1,\ldots,t-1\}:q|j(s-1)+t\right|-\left|j\in \{1,\ldots,t-1\}:q|j(-s-1)+t\right|.$$

Now assume that $rs\equiv 1\pmod q$. Then we have $\mathbf{1}\{q|ts\}=\mathbf{1}\{q|t\}=\mathbf{1}\{q|tr\}$, also $q|j(s-1)+t=js+(t-j)$ if and only if $q|(t-j)(r-1)+t=j+(t-j)r\equiv r(js+(t-j))$. Analogously, $q|j(-s-1)+t$ if and only if $q|(t-j)(-r-1)+t$. This yields $B_s(t)-B_s(t-1)=B_r(t)-B_r(t-1)$ and therefore $B_s(t)=B_r(t)$ for all $t$.