\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{psfrag}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}




\begin{center}
\vskip 1cm{\LARGE\bf The Number of Crossings in a Regular \\
\vskip .1in
Drawing of the Complete Bipartite Graph
}
\vskip 1cm
\large
St\'{e}phane Legendre\\
Team of Mathematical Eco-Evolution\\
Ecole Normale Sup\'{e}rieure\\
75005 Paris \\
France \\
\href{mailto:legendre@ens.fr}{\tt legendre@ens.fr} \\
\end{center}

\vskip .2 in

\begin{abstract}
The regular drawing of the complete bipartite graph $K_{n,n}$ produces
a striking pattern comprising simple and multiple crossings. We compute
the number $c(n)$ of crossings and give an asymptotic estimate for this
sequence.
\end{abstract}

%\newtheorem{conjecture}{Conjecture}
%\newtheorem{corollary}{Corollary}
%\newtheorem{proposition}{Proposition}
%\newtheorem{theorem}{Theorem}

\newcommand{\page}[1]{p.~#1}
\newcommand{\eqn}[1]{Eq.~(\ref{#1})}
\newcommand{\scn}[1]{\S\ref{#1}}


\section{Introduction}\label{introduction}

A regular drawing of the complete bipartite graph $K_{n,n}$ is obtained
in the following way. Draw vertically $n$ uniformly spaced nodes on the
left, draw vertically $n$ uniformly spaced nodes on the right, and join
by straight lines the left and right nodes in all possible manners. A
striking pattern appears, as in Figure \ref{fig1}.

This combinatorial pattern is one of many devised by ancient scholars
--- Ramon Lull (circa 1235--1316), Giordano Bruno (1548--1600) and Wilhem
Leibniz (1646--1716) among others --- who aimed at explaining phenomena
in terms of extensive combinations of primordial entities. Athanasius
Kircher (1601--1680) uses the $K_{n,m}$ pattern in several instances in
his book \textit{Ars Magna Sciendi} \cite{kircher}. His drawing of
$K_{18,18}$ is reproduced in the novel \textit{Foucault's Pendulum} by
Umberto Eco \cite{eco}. As the protagonists of the novel delve into
esoteric matters, the $K_{n,n}$ pattern suggests to them that the Map
would be reconstructed, provided that a device could compute all
combinations.

Here we look more prosaically for a formula giving the number $c(n)$ of
crossings in a regular drawing of $K_{n,n}$. Figure \ref{fig1} displays
the first values of $c(n)$.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.6]{fig1.eps}
\caption{Regular drawing of $K_{n,n}$ for $n=2,3,4,5$ and 10, with the corresponding number $c(n)$ of crossings.}
\label{fig1}
\end{center}
\end{figure}

\section{Simple and multiple crossings}\label{crossings}

Let us assume that nodes on the left have integer coordinates $(0,i)$,
$1 \le i \le n$, and nodes on the right have integer coordinates
$(1,j)$, $1 \le j \le n$.

We define an $(a,b)$\textit{-crossing} as the intersection point of two
lines, each joining a left node to a right, where $a$ is the distance
between left nodes, $1 \le a \le n-1$, and $b$ is the distance between
right nodes, $1 \le b \le n-1$.

Let $\langle i,a | j,b \rangle$ denote the $(a,b)$-crossing whose nodes
have ordinates $i$, $i+a$ on the left, $1 \le i < i+a \le n$, and
$j-b$, $j$ on the right, $1 \le j-b < j \le n$, as in Figure
\ref{fig2}. When $a$, $b$, $i$, $j$ are understood from context, we
shall abbreviate $\langle i,a | j,b \rangle$ as $\mathcal{C}$.

\begin{figure}[ht]
\begin{center}
\psfrag{i}{$i$} 
\psfrag{i+a}{$i+a$}
\psfrag{j-b}{$j-b$}
\psfrag{j}{$j$}
\includegraphics[scale=0.3]{fig2.eps}
\caption{An $(a,b)$-crossing.}
\label{fig2}
\end{center}
\end{figure}

A crossing has \textit{multiplicity} $m$ if it is the intersection of
$m+1$ lines. It is \textit{simple} if $m=1$ (two lines intersect),
\textit{multiple} if $m \ge 2$.\

\begin{proposition}\label{Thales}
For given $a$ and $b$, the $(a,b)$-crossings $\langle i,a | j,b \rangle$ have the same abscissa $x=\frac{a}{a+b}$ when $a \le b$, and $x=\frac{b}{a+b}$ when $a > b$, and ordinates $y=\frac{aj+bi}{a+b}$ with $1 \le i \le n-a$ and $b \le j \le n$.
\end{proposition}

\begin{proof} 
By the theorem of Thales, $\frac{x}{a}=\frac{1-x}{b}$ gives the abscissa $x$, and $\frac{(i+a)-(j-b)}{1}=\frac{y-(j-b)}{\frac{b}{a+b}}$ gives the ordinate $y$.
\end{proof}

\begin{corollary}\label{same_x}
The $(a,b)$-crossing $\mathcal{C}$ with $\gcd(a,b)=1$ and the $(a',b')$-crossing $\mathcal{C'}$ have the same abscissa if and only if there exists $d \ge 1$ such that $a'=da$ and $b'=db$.
\end{corollary}

\begin{proof} 
If $\frac{a}{a+b}=\frac{a'}{a'+b'}$ then $ab'=ba'$. As $\gcd(a,b)=1$, $a$ divides $a'$ and $b$ divides $b'$, so that there exist $d \ge 1$ and $e \ge 1$ such that $a'=da$, $b'=eb$. As $ab'=ba'$, we get $d=e$. The converse is obvious. 
\end{proof}

\begin{corollary}\label{(n-a)(n-b)}
When disregarding superimposition, the number of $(a,b)$-crossings is $(n-a)(n-b)$.
\end{corollary}

\begin{proof}
From Proposition \ref{Thales}, $i$ can take $n-a$ values and $j$ can take $n-b$ values.
\end{proof}

\begin{proposition}\label{da,db}
Let $\mathcal{C}=\langle i,a | j,b \rangle$ be an $(a,b)$-crossing with $\gcd(a,b)=1$, and $\mathcal{C'}=\langle i',da | j',db \rangle$ a $(da,db)$-crossing with $d \ge 1$. Then $\mathcal{C}$ and  $\mathcal{C'}$ are superimposed if and only if there exists $k \in \mathbb{Z}$ such that $i'=i+ka$ and $j'=j-kb$.
\end{proposition}

\begin{proof} 
Crossings $\mathcal{C}$ and $\mathcal{C'}$ have the same abscissa by
Corollary \ref{same_x}. By Proposition \ref{Thales}, they have the same
ordinate if and only if $aj+bi=aj'+bi'$, or $a(j-j')=b(i'-i)$. As
$\gcd(a,b)=1$, the latter condition is equivalent to the existence of
$k \in \mathbb{Z}$ such that $i'-i=ka$ and $j'-j=-kb$.
\end{proof}

\begin{corollary}\label{simple}
If an $(a,b)$-crossings is simple then $\gcd(a,b)=1$. Every multiple crossing contains an $(a,b)$-crossing such that $\gcd(a,b)=1$.
\end{corollary}

\begin{proof} 
Assume that $\mathcal{C}=\langle i,a | j,b \rangle$ is simple and that there exist $d \ge 2$ and $a'$, $b'$ such that $a=da'$, $b=db'$. Then the $(a',b')$-crossing $\mathcal{C'}=\langle i',a' | j',b' \rangle$ with $i'=i$ and $j'=j$ is superimposed on $\mathcal{C}$ by Proposition \ref{da,db}, contradicting simplicity. Hence $\gcd(a,b)=1$. Let $\mathcal{C'}=\langle i,a' | j,b' \rangle$ be an $(a',b')$-crossing contained in a multiple crossing. We set $d=\gcd(a',b')$, $a=a'/d$, and $b=b'/d$. Then the crossing $\mathcal{C}=\langle i,a | j,b \rangle$ has the desired properties by Proposition \ref{da,db}. 
\end{proof}

\begin{figure}[ht]
\begin{center}
\psfrag{i}{$i$} 
\psfrag{i+a}{$i+a$}
\psfrag{i+2a}{$i+2a$}
\psfrag{i+3a}{$i+3a$}
\psfrag{j-3b}{$j-3b$}
\psfrag{j-2b}{$j-2b$}
\psfrag{j-b}{$j-b$}
\psfrag{j}{$j$}
\includegraphics[scale=0.3]{fig3.eps}
\caption{A multiple crossing.}
\label{fig3}
\end{center}
\end{figure}

\begin{proposition}\label{multiple}
Suppose $\mathcal{C}$ is an $(a,b)$-crossing with $\gcd(a,b)=1$, superimposed to a multiple crossing $\mathcal{M}$ of multiplicity $m \ge 2$. Then $1 \le ma \le n-1$ and $1 \le mb \le n-1$. In particular, $2a \le n-1$ and $2b \le n-1$. Moreover, $\mathcal{M}$ is the superimposition of $m$ $(a,b)$-crossings, $m-1$ $(2a,2b)$-crossings, $m-2$ $(3a,3b)$-crossings, \ldots, and a single $(ma,mb)$-crossing.
\end{proposition}

Figure \ref{fig3} displays a crossing of multiplicity $m=3$. It is the superimposition of three $(2,3)$-crossings, two $(4,6)$-crossings and one $(6,9)$-crossing.\

\begin{proof} 
Among the $(a,b)$-crossings contained in $\mathcal{M}$, we select $\langle i,a | j,b \rangle$ with $i+a \le n$ and $1 \le j-b$, such that $i$ is minimum and $j$ is maximum. For $k=1,\ldots, m$, the $m$ $(a,b)$-crossings $\langle i+(k-1)a,a | j-(k-1)b,b \rangle$ are superimposed to $\mathcal{M}$ by Proposition \ref{da,db}. For $k=m$, $i+ma \le n$ gives $ma \le n-i \le n-1$, while $1 \le j-mb$ and $j \le n$ give $ mb \le n-1$. Moreover,
for $k=1,\ldots,m-1$, the $m-1$ $(2a,2b)$-crossings  $\langle i+(k-1)a,2a | j-(k-1)b,2b \rangle$ are superimposed to $\mathcal{M}$, \ldots, and the $(ma,mb)$-crossing $\langle i,ma | j,mb \rangle$ is superimposed to $\mathcal{M}$. 
\end{proof}

\begin{corollary}\label{gcd}
The multiplicity of a $(u,v)$-crossing that is not superimposed to another $(u,v)$-crossing, is the greatest common divisor of $u$ and $v$.
\end{corollary}
\begin{proof} 
This is a consequence of Corollary \ref{simple} and Proposition \ref{multiple}.
\end{proof}

\begin{proposition}\label{count}
The number of crossings of abscissa $\frac{a}{a+b}$ (or $\frac{b}{a+b}$) with $\gcd(a,b)=1$ is
\begin{eqnarray}
\nonumber &(n-a)(n-b)-(n-2a)(n-2b), \hspace{6pt} &\text{if } 2a \le n-1 \text{ and } 2b \le n-1;\\
\nonumber &(n-a)(n-b), \hspace{6pt} &\text{otherwise}.
\end{eqnarray}
\end{proposition}

\begin{proof}
The crossings of abscissa  $\frac{a}{a+b}$ are simple or multiple. If
they are all simple, their number is $(n-a)(n-b)$ by Corollary
\ref{(n-a)(n-b)}, and this occurs when $2a>n-1$ or $2b>n-1$ by
Proposition \ref{multiple}. If some crossings are simple and others are
multiple, then $2a \le n-1$ and $2b \le n-1$ by Proposition
\ref{multiple}. Each simple crossing is counted one time in the first
term, and 0 times in the second term. Indeed, the second term is the
number of $(2a,2b)$-crossings (disregarding superimposition), and they
are not simple by Corollary \ref{simple}. By Proposition
\ref{multiple}, each multiple crossing of multiplicity $m$ contributes
$m$ to the first term and $m-1$ to the second term, hence contributes
$m-(m-1)=1$ to the tally.
\end{proof}

\section{Number of crossings}\label{number}

We now state our main result.

\begin{proposition}\label{count_all}
The number $c(n)$ of crossings in a regular drawing of the complete bipartite graph $K_{n,n}$ is
\begin{displaymath}
c(n)=\sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}(n-a)(n-b)-\sum_{\substack{1 \le 2a,2b \le n-1\\\gcd(a,b)=1}}(n-2a)(n-2b).
\end{displaymath}
\end{proposition}

\begin{proof} 
As each crossing in the drawing contains an $(a,b)$-crossing with $\gcd(a,b)=1$ by Corollary \ref{simple}, we count the number of crossings using Proposition \ref{count}. Summing over all $(a,b)$ such that $\gcd(a,b)=1$, within the bounds of validity, gives the result. 
\end{proof}

An alternative expression for $c(n)$ has been proposed by Philippe Paclet \cite{paclet}:

\begin{proposition}\label{count_all_paclet}
Let $f(i,j)$ be the number of irreducible fractions $p/q$ with $1 \le p \le i$ and $1 \le q \le j$, and $f'(i,j)$ the number of rationals admitting at least one reducible form $p/q$ with $1 \le p \le i$ and $1 \le q \le j$. Then
\begin{displaymath} 
c(n)=\sum_{1 \le i,j \le n-1}(f(i,j)-f'(i,j)).
\end{displaymath}
\end{proposition}

\begin{proof} 
We denote
\begin{displaymath}
s(n)=\sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}(n-a)(n-b), \hspace{6pt} s'(n)=\sum_{\substack{1 \le 2a,2b \le n-1\\\gcd(a,b)=1}}(n-2a)(n-2b),
\end{displaymath} 
so that $c(n)=s(n)-s'(n)$. By the definition of $f$,
\begin{displaymath}
\sum_{1 \le i,j \le n-1}f(i,j) = \sum_{1 \le i,j \le n-1}\sum_{\substack{1 \le a \le i\\ 1 \le b \le j\\ \gcd(a,b)=1}} 1 = \sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}\sum_{\substack{a \le i \le n-1\\ b \le j \le n-1}} 1 = \sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}(n-a)(n-b)=s(n).
\end{displaymath}
Similarly,
\begin{displaymath}
\sum_{1 \le i,j \le n-1}f'(i,j) = \sum_{\substack{1 \le c,d \le n-1\\ \gcd(c,d)\neq 1}}\sum_{\substack{c \le i \le n-1\\ d \le j \le n-1}} 1.
\end{displaymath}
The set $\{(c,d);1 \le c,d \le n-1, \gcd(c,d)\neq 1\}$ is identical to the set  $\{(a,b);1 \le 2a,2b \le n-1, \gcd(a,b)=1\}$. Indeed, $\gcd(c,d)\neq 1$ is equivalent to the existence of $m \geq 2$ such that $c=ma$, $d=mb$, with $\gcd(a,b)=1$, $2a \le ma \le n-1$, $2b \le mb \le n-1$. We obtain
\begin{displaymath}
\sum_{1 \le i,j \le n-1}f'(i,j) = \sum_{\substack{1 \le 2a,2b \le n-1\\ \gcd(a,b)=1}}(n-2a)(n-2b)=s'(n).
\end{displaymath}
\end{proof} 

Sequence $s(n)$ is \seqnum{A115004} in Sloane \cite{oeis}. Values of $c(n)$ are given in Table \ref{table}.

\begin{table}[ht]
\footnotesize
\begin{center}
\begin{tabular}{| l | c c c c |}
\hline
$n$     &$s(n)$   &$s'(n)$  &$c(n)$    &$d(n)$\\
\hline
1       &-        &-        &0         &0\\
2       &1        &0        &1         &1\\
3       &8        &1        &7         &9\\
4       &31       &4        &27        &36\\
5       &80       &15       &65        &100\\
6       &179      &32       &147       &225\\
7       &332      &71       &261       &441\\
8       &585      &124      &461       &784\\
9       &948      &211      &737       &1296\\
10      &1463     &320      &1143      &2025\\
11      &2136     &499      &1637      &3025\\
12      &3065     &716      &2349      &4356\\
13      &4216     &999      &3217      &6084\\
14      &5729     &1328     &4401      &8281\\
15      &7568     &1799     &5769      &11025\\
16      &9797     &2340     &7457      &14400\\
17      &12456    &3023     &9433      &18496\\
18      &15737    &3792     &11945     &23409\\
\ldots  &\ldots   &\ldots   &\ldots    &\ldots\\
50      &948514   &235680   &712835    &1600625\\
\ldots  &\ldots   &\ldots   &\ldots    &\ldots\\
100     &15189547 &3794060  &11395487  &24502500\\
\hline
\end{tabular}
\end{center}

\caption{The number of crossings $c(n)=s(n)-s'(n)$ in the regular $K_{n,n}$ pattern. The sequence of triangular numbers squared, $d(n)$, enumerates the crossings when disregarding multiplicity.}
\label{table}
\end{table}

\section{Asymptotics}\label{asymptotics}

When disregarding multiplicity, the number of crossings in the $K_{n,n}$ pattern is 
\begin{displaymath}
d(n)={{n}\choose{2}}{{n}\choose{2}}=\frac{n^{2}(n-1)^{2}}{4},
\end{displaymath}
the square of the $n$th triangular number (\seqnum{A000537}).

\begin{proposition}\label{equiv}
For large $n$, $c(n) \sim \frac{9}{2\pi^{2}}d(n)$.
\end{proposition}

\begin{proof} 
We write
\begin{displaymath}
\sum_{1 \le a,b \le n-1}(n-a)(n-b)=n^{2}\sum 1-n\sum(a+b)+\sum ab
\end{displaymath}
with no condition of relative primality under the sums. We have
\begin{displaymath}
\sum (n-a)(n-b)=\sum ab=\frac{n^{2}(n-1)^{2}}{4}=d(n).
\end{displaymath}
Hence $n^{2}\sum 1 - n\sum(a+b)=0$. We now sum with the condition $\gcd(a,b)=1$. As the probability that two positive integers are relatively prime is $\frac{6}{\pi^{2}}$, for large $n$:
\begin{displaymath}
\sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}ab \sim \frac{6}{\pi^{2}}d(n), \text{ and }
n^{2}\sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}1-n\sum_{\substack{1 \le a,b \le n-1\\ \gcd(a,b)=1}}(a+b) \sim 0.
\end{displaymath}
Hence
\begin{displaymath} 
s(n) \sim \frac{6}{\pi^{2}}d(n). 
\end{displaymath}
Let $m=\lfloor \frac{n+1}{2}\rfloor$, then
\begin{displaymath}
\sum_{1 \le a,b \le m-1}(n-2a)(n-2b)= n^{2}(m-1)^{2}-2mn(m-1)^{2}+4\frac{m^{2}(m-1)^{2}}{4}.
\end{displaymath}
We sum with the condition $\gcd(a,b)=1$. For large $n$, $m \sim \frac{n}{2}$. As in the previous computation, the first two terms $\sim 0$, and the last term $s'(n) \sim \frac{6}{\pi^{2}}4d(\frac{n}{2}) \sim \frac{6}{\pi^{2}}4\frac{d(n)}{16}$. We obtain
\begin{displaymath}
s'(n) \sim \frac{1}{4} s(n), 
\end{displaymath}
and $c(n)=s(n)-s'(n) \sim \frac{9}{2\pi^{2}}d(n)$.
\end{proof}

The equivalence $c(n) \sim \frac{9}{8\pi^{2}}n^{4}$, deduced from
Proposition \ref{equiv}, appears to give a better estimate of $c(n)$.
However, the approximation $\pi \approx
\frac{3}{2}\frac{n^{2}}{\sqrt{2c(n)}}$ is not close; e.g., for $n=100$,
the approximation is $3.1420$.

\section{Concluding remarks}

The regular drawing of $K_{n,n}$ can be considered an analogic device
to compute the greatest common divisor of two positive integers $a$ and
$b$. In the drawing, take $a$ units on the left, and $b$ units on the
right. Consider the corresponding $(a,b)$-crossing ($i=0$, $j=b$). Then
the multiplicity $m$ of this crossing is the greatest common divisor of
$a$ and $b$ (Corollary \ref{gcd}).

It can be noted that the abscissas of the $(a,b)$-crossings are Farey
fractions. This suggests that number theoretical properties of the
complete bipartite graph pattern deserve further exploration.

\section{Acknowledgements}

The referee is gratefully acknowledged for constructive suggestions
that improved the manuscript.

\begin{thebibliography}{99}

\bibitem{kircher}
Athanasius Kircher,
\emph{Ars Magna Sciendi, XII Libros Digesta, qua Nova et Universali Methodo per Artificiosum Combinationum Contextum de Omni Re Proposita Plurimis et Prope Infinitis Rationibus Disputari, Omniumque Summaria Quaedam Cognitio Comparari Potest}, Apud Joannem Janssonium a Waesberge and Viduam Elizei Weyerstraet, Amsterdam, 1669.

\bibitem{eco}
Umberto Ecco, \emph{Foucault's Pendulum}, Harcourt Brace Jovanovich, San Diego, 1989, p.\ 473. 

\bibitem{paclet}
Philippe Paclet,
personnal communication, February 20, 2004.

\bibitem{oeis}
Neil Sloane,
The On-Line Encyclopedia of Integer Sequences,\\ \url{http://www.research.att.com/~njas/sequences}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 \textit{Mathematics Subject Classification}: Primary 05C62; Secondary 11A05.

\noindent \textit{Keywords}: complete bipartite graph, greatest common divisor.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000537},
\seqnum{A115004},
and
\seqnum{A159065}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 20 2009;
revised version received  July 10 2009.
Published in {\it Journal of Integer Sequences}, July 10 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}