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

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.

• The question originated indeed by an Ehrhart theoretic approach to a number-theoretic problem. In fact the proof I have so far is in that language, but I would like to see your approach. If it simplifies or shortens what I have it could be very very nice (I did all the computations by hand using Dedekind-Rademacher sums and patience). Feb 25, 2021 at 19:44
• Apologies for taking so long. I finally had some time to sit down and remember what the story of this problem was and turn my comment into an answer. Apr 11, 2021 at 6:10

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.

• Thank you very much. This is (an equivalent version of) the problem from where I came from originally, and my proof was essentially following the lines of that of Yamamoto's (in my case it was lengthier and less transparent, but relying on the same fact you pointed out). Apr 11, 2021 at 8:35
• Also, I want to point out that your digression about the history of the problem is really interesting! Apr 11, 2021 at 8:37

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$$.

• Thank you Fedor. Your proof is indeed shorter than mine. Unless someone comes up with a proof of the other implication (which I think will not happen), the bounty will be awarded to you. :) Feb 25, 2021 at 14:40
• You can also quite easily get this part from the discrete Fourier decomposition $-q\{t/q\}=-\frac {q-1}2+\sum_{z^q=1,z\ne 1}\frac{z^t}{1-z^{-1}}$, which looks promising for both directions but the case of composite $q$ still baffles me when I'm trying to prove the other part. Feb 26, 2021 at 3:18