Area-differences for lattice triangles in a checkerboard

Question

For positive integers $m$ and $n$, what is the integral of the function $(-1)^{\lfloor x \rfloor + \lfloor y \rfloor}$ on the triangle with vertices $(0,0)$, $(m,0)$, and $(0,n)$?

Pictorially, we are putting a red/black checkerboard coloring on the plane and finding the signed difference between the red region enclosed by the triangle and the black region enclosed by the triangle.

Call this integral $I(m,n)$. Here are some values of $I(m,n)$ (if my calculations of signed sums of areas of little triangles and trapezoids are correct):

$\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 \\ 2 & 1/2 & 0 & -1/6 & 0 & 1/10 \\ 3 & 1/2 & -1/6 & 1/2 & 5/6 & 1/2 \\ 4 & 1/2 & 0 & 5/6 & 0 & -1/2 \\ 5 & 1/2 & 1/10 & 1/2 & -1/2 & 1/2 \end{array}$

It would be good to tabulate more values. Can any computer algebra systems handle such computations for specific $m,n$?

Obviously $I(m,n) = I(n,m)$, and an easy telescoping-sum argument shows that $I(1,n)=1/2$. A symmetry argument shows that $I(m,n)=1/2$ when $m$ and $n$ are both odd, and from this it can be proved that $I(m,n)=0$ when $m$ and $n$ are both even. The values of $I(m,n)$ where $m$ and $n$ have opposite parity seem more subtle.

Answer 1

Define $$ h(x)=(-1)^{\lfloor x\rfloor}\, (x-\lfloor x\rfloor)(x-\lfloor x\rfloor-1) $$ Then we have $$I(n,m)= \frac{{\rm Mod}(n,2)}{2}+\frac{n}{m} \sum_{j=1}^{n-1} (-1)^{n-j} \, h\left(\frac{jm}{n}\right)$$ Proof: We use the two primitives \begin{eqnarray*} f(y)=\int_0^y dx\, (-1)^{\lfloor x\rfloor} &=& {\rm Mod}(y,2)+(-1)^{\lfloor y\rfloor}\,(y-\lfloor y\rfloor)\\ g(z)=\int_0^z dy \int_0^y dx\, (-1)^{\lfloor x\rfloor}&=& \frac{z}{2}+(-1)^{\lfloor z\rfloor}\, \frac{(z-\lfloor z\rfloor)(z-\lfloor z\rfloor-1)}{2} \end{eqnarray*} to rewrite \begin{eqnarray*} I(n,m)&=& \int_0^n dx (-1)^{\lfloor x\rfloor}\, f(m-x \frac{m}{n}) =\frac{n}{m} \int_0^m dt (-1)^{\lfloor n-t \frac{n}{m}\rfloor}\, f(t)\\ &=&\frac{n}{m} \sum_{j=1}^{n-1} (-1)^{n-j-1}\, \left\{g\left(\frac{(j+1)m}{n}\right)-g\left(\frac{j m}{n}\right)\right\}\\ &=&\frac{{\rm Mod}(n,2)}{2}+\frac{n}{m} \sum_{j=1}^{n-1} (-1)^{n-j}\, h\left(\frac{jm}{n}\right) \end{eqnarray*} where we first performed a change of variables $t=m-x m/n$, and then decomposed the integral over intervals $(j\frac{m}{n},(j+1)\frac{m}{n}]$, over which $\lfloor n-t \frac{n}{m}\rfloor=n-j-1$.

Note that using the 2-periodicity of $h$ we get immediately $$m \,I(n,m)=(m+2n)\,I(n,m+2n)-n \,{\rm Mod}(n,2).$$ Note also that $h$ is an odd function, so that: $$m\, I(n,m)+(2n-m)I(n,2n-m)=n\, {\rm Mod}(n,2) .$$

Another consequence of $h(2-x)=-h(x)$ is: $$I(k n,k(n-s))={\rm Mod}(k,2)\, I(n,n-s)$$ for odd $s$, and the explicit formula: $$I(k n,k(n-1))={\rm Mod}(k,2)\, I(n,n-1)=\frac{{\rm Mod}(k,2)}{2}\left( {\rm Mod}(n,2)+(-1)^n \frac{n+1}{3}\right) .$$ Proof: Define $c(n,m,k)=\sum_{j=k+1}^{k+n-1} (-1)^{n-j}\,h(jm/n)$, then by the above property of $h$, we have $$c(n,m,n)+c(n,m,2n)=\sum_{j=n+1}^{3n-1} (-1)^{n-j}\, h(jm/n)=0$$ by using the $j\to 4n-j$ symmetry, and $h(2m)=0$. We deduce that for $k$ odd: $$ c(kn,k(n-s),0)=\sum_{j=1}^{kn-1} (-1)^{n-j}h(j(n-s)/n)=\sum_{j=1}^{n-1}(-1)^{n-j}h(j(n-s)/n)=c(n,n-s,0)$$ while it vanishes for $k$ even. The above formula follows from $I(n,m)={\rm Mod}(n,2)/2+(n/m)c(n,m,0)$.

Finally, for $s=1$, noting that $\lfloor j(n-1)/n\rfloor]=j-1$ for $1\leq j\leq n-1$, we have: $$c(n,n-1,0)=\sum_{j=1}^{n-1}(-1)^{n-j+j-1}\frac{-j(n-j)}{n^2}=(-1)^n\,\frac{n^2-1}{6 n}$$ and the above formula follows.

Answer 2

As discussed elsewhere, $f(m,n) := mn\, I(m,n)$ is a natural thing to focus on (eg, because it's an integer when $m$ and $n$ have opposite parity), so let's focus on computing it. In this answer by Philippe Di Francesco, the following two claims are proven:

Claim 1. $f(m,n) = f(m,n-2m)$ if $m$ is even.

Claim 2. $f(m,n) = n^2 + f(m-2n,n)$ if $n$ is odd.

I have chosen to write these identities asymmetrically here, but of course they're true in more generality. The purpose of this presentation is to show that they are very useful for reduction of $f(m,n)$ in the case that $m$ is even and $n$ is odd.

Moreover, if we extend the definition to negative $m$ and $n$ so that $f(-m,n)=-f(m,n)$ and $f(m,-n)=-f(m,n)$, these claims continue to hold. As a result, the first claim can be used to first reduce $n$ to the range $-m \le n \le m$, and thus to $0\le n\le m$. Also, the second claim can be used to reduce $m$ to the range $-n\le m\le n$, and thus to $0\le m\le n$. (The identities also resolve the case $m=n$.)

Restricting to the case of $m$ even and $n$ odd, one could express this as follows: $$ f(m,n) = \begin{cases} \operatorname{sign}(m) \operatorname{sign}(n) f(\lvert m\rvert, \lvert n\rvert) & \text{if $m \le 0$ or $n \le 0$,} \\ f(m,n-2m) & \text{if $n>m$,} \\ n^2 + f(m-2n,n) & \text{else.} \end{cases} $$ $$ I(m,n) = \frac{f(m,n)}{mn}. $$

The following simple Mathematica code implements this idea straightforwardly, for all $m$ and $n$ regardless of parity considerations:

f[m_,n_]:=Which[
  m*n==0, 0,
  m<0, -f[-m,n],
  n<0, -f[m,-n],
  m==n, Mod[n,2]*n^2/2,
  n>m, Mod[m,2]*m^2 + f[m,n-2m],
  True, Mod[n,2]*n^2 + f[m-2n,n]
]
i[m_,n_] := f[m,n] / (m*n)
Table[i[m,n],{m,1,5},{n,1,5}]//TableForm

These various reductions, effectively of things like $m\bmod(2n)$, can be taken "all the way", allowing for the following more efficient but uglier code:

sumsquares[n_,d_,k_]:=(1+k)*(2*d^2*k+4*(d*k)^2-6*d*k*n+3*n^2)/3
f[m_,n_]:=Which[
  m*n==0 || Mod[m,2]==Mod[n,2], Mod[m,2]*m*n/2,
  m<0 || n<0, Sign[m]*Sign[n]*f[Abs[m],Abs[n]],
  Mod[n,2]==1 && m>n>m*2/3, sumsquares[n,m-n,Floor[n/(2*(m-n))]]+f[Mod[n,2*(m-n)]-2*(m-n),Mod[n,2*(m-n)]-(m-n)],
  True, Mod[n,2]*n^2*Floor[m/(2*n)+1/2]+f[n,Mod[m+n,2*n]-n]
]
i[m_,n_]:=f[m,n]/(m*n)
Table[i[m,n],{m,1,5},{n,1,5}]//TableForm

This runs very quickly even for large $m$ and $n$, as it uses a recurrence resembling the Euclidean algorithm. As Peter Taylor noted in the comments earlier, previous versions ran in linear time in the worst case; however, this latest version is worst-case logarithmic time. The improvement is to handle the case when $m$ and $n$ are very similar in size by summing a bunch of odd squares explicitly.

Answer 3

It appears that $I(m,n) = f(m) + g(m,r)/(mn)$, where $f(m) = 0$ if $m$ is even, $1/2$ if $m$ is odd and $r = n$ mod $2m$.

(Note that I have not proved this, only observed it.)

Here are some of the values of $g$:

\begin{eqnarray*} g(1,r) & = & (0, 0) \\ g(2,r) & = & (0, 1, 0, -1) \\ g(3,r) & = & (0, 0, -4, 0, 4, 0) \\ g(4,r) & = & (0, 2, 0, 10, 0, -10, 0, -2) \\ g(5,r) & = & (0, 0, -4, 0, -20, 0, 20, 0, 4, 0) \\ g(6,r) & = & (0, 3, 0, 9, 0, 35, 0, -35, 0, -9, 0, -3) \\ g(7,r) & = & (0, 0, -8, 0, -16, 0, -56, 0, 56, 0, 16, 0, 8, 0) \\ g(8,r) & = & (0, 4, 0, 8, 0, 24, 0, 84, 0, -84, 0, -24, 0, -8, 0, -4) \\ g(9,r) & = & (0, 0, -8, 0, -16, 0, -36, 0, -120, 0, 120, 0, 36, 0, 16, 0, 8, 0) \\ g(10,r) & = & (0, 5, 0, 19, 0, 25, 0, 51, 0, 165, 0, -165, 0, -51, 0, -25, 0, -19, 0, -5) \\ g(11,r) & = & (0, 0, -12, 0, -12, 0, -36, 0, -68, 0, -220, 0, 220, 0, 68, 0, 36, 0, 12, 0, 12, 0) \\ g(12,r) & = & (0, 6, 0, 18, 0, 26, 0, 50, 0, 90, 0, 286, 0, -286, 0, -90, 0, -50, 0, -26, 0, -18, 0, -6) \end{eqnarray*}

So "all" that remains is to derive a formula for $g$ (and to prove that $I$ has this form). Note that there is an observed symmetry, $g(m,r) = -g(m,2m-r)$.

Here are some further observations about $g$:

Let $l = 2ki + j$, where $0 \leq j < 2k$. Then we know: \begin{eqnarray*} g(2k,2l+1)/((2k)(2l+1)) & = & f(2k,2l+1) \\ & = & f(2l+1,2k) \\ & = & 1/2 + g(2l+1,2k)/((2k)(2l+1)) \end{eqnarray*}

So, when $r=2j+1$ is odd and $r < 4k$, $g(2k,r) = k(4ki+r) + g(4ki+r,2k)$.

This means that we can derive the odd rows of $g$ from the even rows (or vice versa): $g(2t+1,2k) = g(2k,(2t+1 \ {\rm mod} \ 4k)) - k(2t+1)$.

E.g., $g(11,8) = g(8,11) - 4 \cdot 11$, $-68 = -24 - 44$, or $g(11,4) = g(4,3) - 2 \cdot 11$, $-12 = 10 - 22$.

If we also use the relation $g(2t+1,2k) = -g(2t+1,4t+2-2k)$, $g(2k,(2t+1 \ {\rm mod} \ 4k)) - k(2t+1) = -g(4t+2-2k,(2t+1 \ {\rm mod} \ 8t+4-4k)) + (2t+1-k)(2t+1)$.

Then this gives us relations between even rows of $g$: $g(2k,(2t+1 \ {\rm mod} \ 4k)) = (2t+1)^2 - g(4t+2-2k,(2t+1 \ {\rm mod} \ 8t+4-4k))$

E.g., when $k=6$ and $t=3$: $g(12,7 \ {\rm mod} \ 24) = 7^2 - g(2,7 \ {\rm mod} 4)$, $50 = 49 - (-1)$. Or when $k=6$ and $t=4$: $g(12,9 \ {\rm mod} \ 24) = 9^2 - g(6,9 \ {\rm mod} \ 12)$, $90 = 81 - (-9)$.

This might give us an effective way to compute $g$ recursively. E.g., once we have $g(12,9) = 81 - g(6,9)$ we can then continue to observe that $g(6,9) = -g(6,3)$, $g(6,3) = g(0,3 \ {\rm mod} \ 0) + 3^2$ to finally conclude $g(12,9) = 81 - (- (0 + 9)) = 90$.

Answer 4

This extends a comment of Fedor Petrov:\ The function $s(x)=(-1)^{\lfloor x\rfloor}$ has the Fourier expansion $$s(x)~=~ \frac{4}{\pi} \sum \limits_{k=1}^\infty \frac{\sin (2k-1) \pi x}{2k-1}.$$ The question asks for the value of the integral $$I(m,n) ~=~ \int \limits_{x=0}^n \int\limits_{y=0}^{m(1-x/n)} s(x)\,s(y)\,dy\,dx.$$ By defining $$a(n,m,k,j)~=~ \int \limits_{x=0}^n \int\limits_{y=0}^{m(1-x/n)} \sin\left[ (2k-1) \pi x\right]\,\sin\left[ (2j-1) \pi y\right]\,dy\,dx,$$ one obtains for $(2j-1)m\neq(2k-1)n$
$$a(n,m,k,j)~=~ \frac{2}{(2k-1)(2j-1) \pi^2}\left([n~{\rm odd}] -(-1)^m [n+m ~{\rm odd}]\frac{(2k-1)^2 n^2}{(2k-1)^2 n^2- (2j-1)^2 m^2} \right).$$ If $(2j-1)m=(2k-1)n$ one has $$a(n,m,k,j)~=~[n~{\rm odd}] \frac{2 m}{(2k-1)^2 n \pi^2}. $$ Together one obtains $$I(m,n)~=~ \frac{16}{\pi^2}\sum \limits_{k,j=1}^\infty \frac{a(n,m,k,j)}{(2k-1)(2j-1) }$$ This immediately gives $I(2 m,2n)=0$ and after some calculation also $I(2m+1,2n+1)=1/2$. The case $I(2m+1,2n)$ is more complicated, but simplification gives the series $$I(2m+1,2n) ~=~ \frac{8}{\pi^3\,x} \sum \limits_{j=1}^\infty \frac{\tan\left(\frac{\pi x}{2}(2j-1)\right)}{(2j-1)^3},$$ where $x= (2m+1)/(2n)$.

Answer 5

Some people have noticed that $mnI(m,n)$ is an integer when $m, n$ opposite parity. It is actually proved in jcdornano's reply with a nice argument I think. As it might not be very clearly expressed, I took the liberty to rewrite it here.

Let $m$ be even number and let $T$ be the triangle of vertices $(0,0)$, $(m,0)$, and $(0,n)$ with a black and white coloring $C$ as explained in the initial post. Let us consider $L$ the linear application that multiplies the absiceas by $n$ and the ordinates by $m$ and let us consider $T' $ the image of $T$ by $L$. $L$ naturally induces a coloring $C'$ on $T'$: the images of the black subset of $T$ is a black subset of $T'$ and the images of the white subset of $T$ is a white subset of $T'$.

Language convention: Let $X$ be any black and white coloring of the plane. we can associates to $X$ a function $f $ whose value is $1$ on the white parts and $-1$ on the black parts. By abuse, we will speak of the integral of $X$ to mean the itegral of $f$.

Let $I' $ be the integral of $C'$ on $T'$. It is immediate that $I(n,m)=I'/mn$. To prove that $I(n,m).nm$ is an integer, we just have to prove that $ I' $ is an integer.

Let us prove this fact. Since $T'$ is isocele, the points of its hypothenus with integer ordinate also have an integer absicea. Let us denote these points by $A_0, A_1, A_2, ..., A_{nm}$. For any $0\leq i\leq nm-1$, let $T_i$ be the right triangle whose hypothenuse is $[A_i A_{i+1}]$.

$T'$ is the union of :

• $\cup_{i=1}^{nm} T_i$
• $S = T'\setminus \cup_{i=1}^{nm}T_i$.

Let $I_1$ be the integal of $C'$ on $S$ and let $I_2$ be the integal of $C'$ on $ \cup_{i=1}^{nm} T_i$. $I' = I_1+I_2$. Let us prove that $I_1=0 $ et that $ I_2$ is an integer.

Because the points $A_i$ have integers coordinates, $S$ is the union of squares of the form $[j,j+1]*[k,k+1]$ where $j,k\in \mathbb N$. Since such squares are either entirerly white or entirerly black, the value of the integral of $C'$ on them is $1 $ or $-1$ and the integral of C' on S in an integer.

Let us now prove that $I_2 $ is equal to $0$. Because $T' $ is an isocele triangle , all the triangles $T_i $ are isometrics one to the other. There are an even number of them with half of them being black while the other half being white. Hence they "compensate" each other and $I_2=0$.

Answer 6

The following sketchy algorithm should give a (at least probabilistically) fast algorithm for computing $I(m,n)$:

First step: Using comments and easy properties it is enough to consider the case where $m$ and $n$ are of different parities and coprime.

Using continued fraction expansions of $-n/m$, we can find an integral vector $(a,b)$ in the open convex hull of $(0,0),(m,0),(0,n)$ such that $(a,b),(m,0),(0,n)$ are vertices of a triangle $\Delta$ of minimal area $1/2$.

We have now $I(m,n)=(ab\pmod 2)+I(m-a,b)+I(a,n-b)+I_\Delta$ where $ab\pmod 2$ is the contribution of the rectangle $[0,a]\times [0,b]$ and where $I_\Delta$ is the contribution coming from $\Delta$.

Exactly one contribution among $I(m-a,b),I(a,n-b)$ has arguments of the same parity and can thus be evaluated trivially.

The triangle $\Delta$ is sort of a very fine needle and the contribution of $I_\Delta$ can be evaluated using continued fraction expansions (essentially linearly with respect to the length of the continued fraction expansion of $m/n$). More precisely, $I_\Delta$ can be computed from the combinatorics of the (periodic) Sturmian words associated to slopes of $m/n,(m-a)/b,a/(n-b)$ (these words are very close because of the needle-like nature of $\Delta$ and they are encoded by the corresponding continued fraction epxansions).

This should give an algorithm evaluating $I(m,n)$ using probabilistically $O(\log(mn))$ arithmetical operations on integers of size at most $\max(m,n)$. The algorithm is only probabilistical since we have no obvious control over the choice of the trivial piece among $I(m-a,b),I(a,n-b)$.

Added: Computing $I_\Delta$ is a bit more tricky than I first thought: There is not only a combinatorial but there are also two metrical parameters. I think it can be done but I am not absolutely sure without writing down all details (lengthy and technical, I fear). Hopefully I will find the time to do it properly.

Answer 7

Let $m_2(x)$ be the remainder of $x$ mod $2$, i.e., $m_2(x) = x - 2\lfloor x/2\rfloor$.

Let $s(x)$ be the periodic step function equal to $1$ if $0\le m_2(x)<1$, or $-1$ otherwise.

Let $t(x)$ be the integral of $s(x)$, equal to $m_2(x)$ if $0\le m_2(x)<1$, or $2-m_2(x)$ otherwise. Note that $t(x)=t(x+2)=t(-x)=1-t(x+1)$, all of which we will use below. This form may also be useful (where $\{x\}=x-\lfloor x\rfloor$): $$t(x)=\frac{1}{2}+(-1)^{\lfloor x\rfloor}\left(\{x\}-\frac{1}{2}\right)$$

Now, we can decompose the triangle into subtriangles of area $1/(2mn)$, each of which contributes $\pm 1/(2mn)$ to the integral: \begin{eqnarray*} I(m,n) &=& \frac{1}{2mn}\sum_{i=0}^{mn-1}\sum_{j=0}^{2mn-2i-2} s\left(\frac{i}{m}\right) s\left(\frac{j}{2n}\right) \\ &=& \frac{1}{m}\sum_{i=0}^{mn-1} s\left(\frac{i}{m}\right) t\left(\frac{2mn-2i-1}{2n}\right) \\ &=& \frac{1}{m}\sum_{i=0}^{mn-1} s\left(\frac{i}{m}\right) t\left((m\bmod 2)+\frac{2i+1}{2n}\right) \\ &=& \frac{1}{m}\sum_{i=0}^{mn-1} s\left(\frac{i}{m}\right) \left(t\left((m\bmod 2)+\frac{i}{n}\right)+\frac{1}{2n}s\left((m\bmod 2)+\frac{i}{n}\right)\right) \\ \end{eqnarray*}

If we assume that $m$ is even, $n$ is odd, and $\gcd(m,n)=1$, then $$I(m,n) = \frac{1}{m}\sum_{i=0}^{mn-1} s\left(\frac{i}{m}\right) \left(t\left(\frac{i}{n}\right)+\frac{1}{2n}s\left(\frac{i}{n}\right)\right)$$

Still assuming that $m$ is even, $n$ is odd, and $\gcd(m,n)=1$, find $a,b$ such that $am+bn=1$. Then we can rewrite the sum over $x,y$, where $i=amy+bnx\bmod mn$ ranges over $\{0,1,\dots,mn-1\}$. (We will repeatedly use that $m$ is even, as well as that $b$ must be odd.) \begin{eqnarray*} I(m,n) &=& \frac{1}{m}\sum_{x=0}^{m-1}\sum_{y=0}^{n-1} s\left(ay+\frac{bnx}{m}\bmod n\right) t\left(\frac{amy}{n}+bx+\frac{1}{2n}\right) \\ &=& \frac{1}{m}\sum_{x=0}^{m-1}\sum_{y=0}^{n-1} s\left(ay+\frac{(1-am)x}{m}\bmod n\right) t\left(\frac{(1-bn)y}{n}+bx+\frac{1}{2n}\right) \\ &=& \frac{1}{m}\sum_{x=0}^{m-1}\sum_{y=0}^{n-1} (-1)^{a(y-x)\bmod n} t\left(bx-by+\frac{y}{n}+\frac{1}{2n}\right) \\ &=& \frac{1}{m}\sum_{x=0}^{m-1}\sum_{y=0}^{n-1} (-1)^{a(y-x)\bmod n} t\left(x-y+\frac{2y+1}{2n}\right) \\ &=& \frac{1}{m}\sum_{x=0}^{m-1}\sum_{y=0}^{n-1} (-1)^{a(y-x)\bmod n} \left(\frac{1}{2}+(-1)^{x-y}\left(\frac{2y+1-n}{2n}\right)\right) \\ &=& \frac{1}{2}+\frac{1}{m}\sum_{x=0}^{m-1}\sum_{y=0}^{n-1} (-1)^{(y-x)+(a(y-x)\bmod n)} \left(\frac{2y+1-n}{2n}\right) \\ \end{eqnarray*}

Let $z=a(y-x)\bmod n$. Then $y-x\equiv mz\pmod{n}$, so $y=x+mz\bmod n$. Now we can rewrite the summation in terms of $z$ rather than $y$: \begin{eqnarray*} I(m,n) &=& \frac{1}{2}+\frac{1}{m}\sum_{x=0}^{m-1}\sum_{z=0}^{n-1} (-1)^{(x+mz\bmod n)-x+z} \left(\frac{2(x+mz\bmod n)+1-n}{2n}\right) \\ &=& \frac{1}{2}+\frac{1}{m}\sum_{x=0}^{m-1}\sum_{z=0}^{n-1} (-1)^{(x+mz-n\lfloor\frac{x+mz}{n}\rfloor)-x+z} \left(\frac{2(x+mz-n\lfloor\frac{x+mz}{n}\rfloor)+1-n}{2n}\right) \\ &=& \frac{1}{2}+\frac{1}{m}\sum_{x=0}^{m-1}\sum_{z=0}^{n-1} (-1)^{z+\lfloor\frac{x+mz}{n}\rfloor} \left(\frac{2x+2mz+1-n}{2n}-\lfloor\frac{x+mz}{n}\rfloor\right) \\ &=& \frac{1}{2}+\frac{1}{m}\sum_{w=0}^{mn-1}(-1)^{\lfloor\frac{w}{m}\rfloor+\lfloor\frac{w}{n}\rfloor} \left(\{\frac{w}{n}\}-\frac{1}{2}+\frac{1}{2n}\right) \\ &=& \frac{1}{2}+\frac{1}{m}\sum_{w=0}^{mn-1}(-1)^{\lfloor\frac{w}{m}\rfloor+\lfloor\frac{w}{n}\rfloor} \{\frac{w}{n}\} \\ &=& \frac{1}{2}+\frac{1}{mn}\sum_{i=0}^{n-1} i \sum_{j=0}^{m-1} (-1)^{j+\lfloor\frac{i+jn}{m}\rfloor} \\ &=& \frac{1}{2}+\frac{1}{mn}\sum_{i=0}^{n-1} i \sum_{j=0}^{m-1} (-1)^{\lfloor\frac{i+j(n-m)}{m}\rfloor} \\ \end{eqnarray*} where first we let $w=x+mz$, and we use the fact that $\sum_{w=0}^{mn-1}(-1)^{\lfloor\frac{w}{m}\rfloor+\lfloor\frac{w}{n}\rfloor}=0$, which follows from $(-1)^{\lfloor\frac{w}{m}\rfloor+\lfloor\frac{w}{n}\rfloor}=-(-1)^{\lfloor\frac{mn-1-w}{m}\rfloor+\lfloor\frac{mn-1-w}{n}\rfloor}$ when $m+n$ is odd, and then we decompose $w$ differently as $w=i+jn$.

This is looking like a nicer formula, and there's probably a more direct route to it, but it's still not clear to me how to convert it to "closed form".

When $m$ is even and $n$ is odd, the periodicity result stated earlier has the following two forms: \begin{eqnarray*} n I(m,n) &=& (n+2m) I(m,n+2m) \\ m I(m,n) &=& (m+2n) I(m+2n,n) - n \end{eqnarray*}

To prove the second periodicity property from the summation formula above, we need to show that $$\sum_{j=0}^{m-1} (-1)^{\lfloor\frac{i+j(n-m)}{m}\rfloor} = \sum_{j=0}^{m+2n-1} (-1)^{\lfloor\frac{i+j(n-(m+2n))}{m+2n}\rfloor}$$ Which seems to be true, but I don't have a proof.

Answer 8

[EDIT : results are feeting with the table given in the question and in the comments by James Propp ... up to a multiplication by -1...this is due to choice of considering $\delta: x=y$ (after applying a linear transformation $diag(n,m)$) instead of the other diagonal $x+y=1$ : indeed see the python code at the end of this post that is the exact translation from the answer]

As $I(m,n)=I(n,m)$ and the case $m-n=0\mod [2]$ has been treated, we suppose wlog that $m$ is even and $n$ is odd. (we will nead this hypothesis in the demonstration)

I clame that :

$mnI(m,n)= \Sigma_{0<i<|D|-1} (c(i)(x_{i+1}-x_i)(2f(i) m-x_i)$ where $D=(n\mathbb N \cup m\mathbb N)\cap [0,mn]=\left\{0=x_0,x_1,...x_{|D|-1}=mn\right\}$ s.t $i\mapsto x_i$ is increasing. where $c(i)=(-1)^{\lfloor x_i/m\rfloor +\lfloor x_i/n\rfloor}$ and where $f(i)=\lfloor (\lfloor x_i/m\rfloor +1)/2\rfloor$

So the $x_i$ in $D$ correspound (up to a multiplcation by $mn$) the abcissas where the diagonal intersects the edges of the squares, $c(i)$ is (up to the normalization that I will discuss futher) the color of the colored "squares" intersected by the diagonal in $x_i$ and $f(i)$ is the number of colored "squares" (intersecting the line $x_i=x$), below the diagonal that are the same color then $c(i)$

note that $mnI(m,n)\in \mathbb Z$

Up to a linear transformation given by a diagonal matrix whose non zero entries are $n$ and $m$ (so we multiply abcissas by $n$ and orinate by $m$), we are dealing with a square $[0,mn]\times [0,mn]$ tilled with red or black colored $m\times n$ rectangles. And we want to get $A(m,n))$ the area of the red (positive) part below the diagonal(*) (the line $\delta : y=x$) minus the area of the black (negative) part below the diagonal $\delta$. To get $I(m,n)$ we will just have to divide $A(m,n)$ by $-mn$. [see EDIT]

(*) to be doing the sommation in a bit more standard way (according to vertical strips rather then horizontal) it seemed to me more convenient (and equivalent) to take $\delta : x=y$ instead of the other diagonal : $y+x=1$

$D$ is then the set of all the abcissas (as well as ordinates) where $\delta$ intersects the edge of some $m\times n$ colored rectangle.

Let $S_i$ be the strip delimited by the lines $x=x_i$ and $x=x_{i+1}$, the part of $S_i$ that is below the diagonal is the (disjoint) union of

1. a trianglwhose hypothenus is $S_i\cap \delta$ and whose (algebraic) area is $T_i=c(i).|T_i|$

2. $f(i)$ rectangles that are the intersection of $m\times n$-rectangle with $S_i$ and whose color is opposite to the sign of $T_i$. The union of these rectangles has algebraic area : $(x_{i+1}-x_i)\times (-c(i)).m.f(i)$

3. rectangles whose color is $c(i)$, the union of these rectangles has area $c(i)(x_{i+1}-x_i)(x_i-f(i)m)$

Then the algebraic area below $\delta$ on each strip is $T_i+c(i)(x_{i+1}-x_i)(-2f(i)m+x_i)$

We can simplify the sommation over strips by noticing that $\Sigma_{0\leq i<|D|-1} T_i=0$, indeed the union of edges of the $T_i$ is stable under symetry wrt the other diagonal ($x+y=1$) of the $[0,mn]\times [0,mn]$ big square, and we can easily see that the color of a triangle is the opposite of that of its symetric. (This is only true because $m$ is even and $n$ odd, if we reverse these hypotheses, it is not true anymore...)

We obtain the anounced formula by noticing that $c(i)=(-1)^{\lfloor x_i/m\rfloor +\lfloor x_i/n\rfloor}$ and $f(i)=\lfloor (\lfloor x_i/m\rfloor +1)/2\rfloor$

(and that that the sum can be inatited to $i=1$, because the firts term of the sommation in $0$)

here is the python code that encode the formula (it only works for $m$ even and $n$ odd)

def D1(m,n):#step for D
    i=0
    A=[]
    while i<n+1:
        A=A+[i*m]
        i=i+1
    return A

def D(m,n): 
    i=0
    A=D1(m,n)
    while i<m :
        if (i*n in D1(m,n))==False :
            A=A+[i*n]
            i=i+1
        else :
            i=i+1
    return sorted (A)

def f(m,x):
    return int((int(x/m)+1)/2)
def c(x,m,n):
    return (-1)**(int(x/m)+int(x/n))
    
def R(m,n,i): #our area on each strip
    x=D(m,n)
    return c(x[i],m,n)*(x[i+1]-x[i])*(x[i]-2*m*f(m,x[i]))
def A(m,n):
    return sum([R(m,n,i) for i in range(len(D(m,n))-1)])

               
def I(m,n):#multiplying by -1 
    return -A(m,n)/(m*n)