3
$\begingroup$

I was taking the determinant of the adjacency matrix for a graph and I stumbled across this interesting (apparent) coincidence:

If $m$ and $n$ are odd numbers, then $$ 2^{\textsf{gcd}(m,n)} = \prod_{k=1}^{m} \prod_{l=1}^{n} \left( e^{\frac{2k\pi i}{m}} + e^{\frac{2 l \pi i}{n}} \right).$$

If we take $\log_2$ of both sides, we get an explicit expression describing the greatest common divisor. Would anyone like to attempt a proof of this fact?

Here is some MATLAB code which checks the above formula. (Save it as a *.m file in your MATLAB directory; then use greatcd(m,n) to output the greatest common divisor of your chosen odd numbers $m$ and $n$.)

function [I,J] = greatcd(m,n)
for k=1:m
for l=1:n
  H(k,l) = exp((2*pi*i*k)/m) + exp((2*pi*i*l)/n);
end
end
G=prod(H(:));
log2(real(G))

It appears that if $g = \textsf{gcd}(m,n)$, then $$\prod_{k=1}^{m} \prod_{l=1}^{n} \left( e^{\frac{2k\pi i}{m}} + e^{\frac{2 l \pi i}{n}} \right) = \prod_{k=1}^{g} \prod_{l=1}^{ng^{-1}} \left( 1 + e^{\frac{2l\pi i}{ng^{-1}}}\right)$$ and I also think that $$ \prod_{l=1}^{ng^{-1}} \left( 1 + e^{\frac{2l\pi i}{ng^{-1}}}\right) = 2.$$ If I hold $l$ fixed and take the product over $k$, I appear to get $$\prod_{k=1}^{m} \left( e^{\frac{2k\pi i}{m}} + e^{\frac{2 l \pi i}{n}} \right) = 1 + e^{\frac{2l\pi i}{ng^{-1}}}.$$

$\endgroup$
  • $\begingroup$ Did you computer-verify it for the first few $m, n$? $\endgroup$ – Shine On You Crazy Diamond Mar 11 '16 at 2:59
  • $\begingroup$ Using Maple, yes $\endgroup$ – Open Season Mar 11 '16 at 3:39
  • $\begingroup$ Do you understand my proof below that your formula is at least a real number? $\endgroup$ – Shine On You Crazy Diamond Mar 11 '16 at 5:25
  • $\begingroup$ I'll have to work out the details myself tomorrow, but it seems to be correct. Thanks for your help! $\endgroup$ – Open Season Mar 11 '16 at 5:31
  • $\begingroup$ No problemo! Thanks for the mathematical observation! $\endgroup$ – Shine On You Crazy Diamond Mar 11 '16 at 5:32
2
$\begingroup$

Here is an "asymmetric" proof. The idea is to introduce an indeterminate $X$ and regard the product as some polynomial evaluated at $X = 1$. The key lemma is that if $m$ is odd and $\zeta$ is an $m$th root of unity then the roots of $p_m(X) := X^m + 1$ are the negatives of the roots of $X^m - 1$, because if $z^m = 1$ then $(-z)^m = (-1)^m z^m = -1$. Therefore, $$p_m(X) = \prod_{k=1}^m (X + \zeta^k).$$ We will use this identity below for $n$ and also for $m/g$, where $g = \text{gcd}(m, n)$.

First, let $\zeta$ and $\eta$ be primitive $m$ and $n$th roots of unity, respectively (e.g. $\zeta = e^{2\pi i / m}$). Introduce $X$, and simplify using the lemma:
$$p(X) = \prod_{k=1}^m \prod_{l=1}^n (\zeta^k X + \eta^l) = \prod_{k=1}^m p_n(\zeta^k X)$$ so
$$\prod_{k=1}^m \prod_{l=1}^n (e^{2\pi i k/m} + e^{2\pi i l/n}) = p(1) = \prod_{k=1}^m p_n(\zeta^k) = (1+\zeta^n)(1+\zeta^{2n})(1+\zeta^{3n})\dotsb(1+\zeta^{mn}).$$

Now because $m$ and $n$ might not be coprime, this product may have repeating terms. But the repetition is very regular. The exponent land is $\mathbb{Z}/m\mathbb{Z}$ (remember, $\zeta$ is an $m$th root of unity) and the map $x \mapsto nx$ has kernel generated by (the equivalence class mod $m$ of) $m/g$. To see this, get $s$ and $t$ such that $ms + nt = g$. If $nx \equiv 0$ (mod $m$) then $ntx = (g - ms)x = gx \equiv 0$ (mod $m$), so $m$ divides $gx$. Since $g$ divides $m$, $m/g$ divides $x$.

Therefore, the whole product is just $g$ copies of the first $m/g$ terms: $$p(1) = [(1+\zeta^n)(1+\zeta^{2n})\dotsb(1+\zeta^{({m/g})n})]^g.$$ There are $m/g$ of these $\zeta$s and they are all $(m/g)$th roots of unity, because $(\zeta^{kn})^{m/g} = (\zeta^m)^{kn/g} = 1$. By the lemma again, $$p(1) = p_{m/g}(1)^g = (1+1)^g$$ and the result follows.

$\endgroup$
2
$\begingroup$

Let $n = 1$ for simplicity.

$\prod\limits_{k,l = 0}^{m-1, n-1} (\exp(\dfrac{2k\pi i}{m}) + \exp(\dfrac{2l\pi i}{n})) = \prod_{k=0}^{m-1} (\exp(\dfrac{2k\pi i}{m}) + 1) = \\\prod\limits_{k=0}^{\dfrac{m-1}{2}}(w^k + 1)\prod\limits_{k=0}^{\dfrac{m-1}{2}}(w^{-k} + 1)$

by symmetry of an odd-sided regular polygon centered at the origin of $\Bbb{C}$ whose vertices are the $m$th roots of unity.

But the rules of complex conjugation yield that $(w^k + 1)^* = (w^{k*} + 1) = w^{-k} + 1$. Thus we have $zz^*$ above and that's always real. Thus for the case $n=1, m\geq 1$ we have proved that the formula is at least a real number.

A similar argument using symmetries of odd-sided regular polygons can be applied to the general case where $n \geq 1, m \geq 1$. Showing that your formula is at least a real number.

Find, that using the same symmetry across the real axis in $\Bbb{C}$ used above that, your general formula is the same as: $$ \prod_{k,l=0}^{\dfrac{m-1}{2}, \dfrac{n-1}{2}}(w^{k} + z^l)(w^{-k}+ z^{-l})(w^{k} + z^{-l})(w^{-k} + z^{l}) $$


Note that $0 \leq |w^{\pm k} + z^{\pm l}| \leq 2$. Which can also be seen by looking at regular unit polygons in the $\Bbb{C}$ plane.

As your formula is a real number, we have that $|\text{formula}| = \pm\text{formula}$.

For all the times in the product when $\dfrac{k}{m} = \dfrac{l}{n}$ you'll get $|w^{k} + z^{l}| = |w^{-k} + z^{-l}| = 2$. Convince yourself this happens iff those two fractions are equal in the product. We're gettin' close!

$\dfrac{k}{m} = \dfrac{l}{n}, \ k,l = 0, \dots, m-1, n-1 \iff ?$

I don't really know, so let's look at an example: $m = 15, n = 9, (m,n) = 3$ $0/15 = 0/9, \ 5/15 = 3/9, \ 10/15 = 6/9$

And those were the only examples I could think of, so it seems like you want to prove that the above happens exactly $\gcd(m,n)$ times in general.

So we have shown so far that $\text{your formula} = \pm 2^{\gcd(m,n)}\prod\limits_{k,l = 0; k/m \neq l/n}^{m-1, n-1} (\dots)$.

We haven't employed rotational symmetry yet, so maybe the answer lies there to prove that the magnitude of the remaining piece of your formula $=1$. And by that I mean multiplying by the terms each by the same $e^{i\pi j/?}$ such that the resulting set of vertices is the same as your original two polygons, also known as a rotational symmetry in a Dihedral group.

$\endgroup$
  • $\begingroup$ I really like your observation that $\textsf{gcd}(m,n) = \# \{(k,l) \Bbb : 1 \leq k \leq m, 1 \leq l \leq n, kn = ml\}.$ $\endgroup$ – Open Season Mar 11 '16 at 14:51
  • $\begingroup$ It seems that if $k$ is the smallest number satisfying the equation $k/m = l/n$, then the greatest common divisor is $m/k$. $\endgroup$ – Open Season Mar 11 '16 at 15:34
  • $\begingroup$ @OpenSeason Thanks! Have you figured out how to prove the rest of the formula equals 1? $\endgroup$ – Shine On You Crazy Diamond Mar 11 '16 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.