text:
# Solitaire Clobber

## 1 Introduction

Clobber is a new two-player combinatorial board game with complete information, recently introduced by Albert, Grossman, and Nowakowski (see ). It is played with black and white stones occupying some subset of the squares of an $`n\times m`$ checkerboard. The two players, White and Black, move alternately by picking up one of their own stones and clobbering an opponent’s stone on a horizontally or vertically adjacent square. The clobbered stone is removed from the board and replaced by the stone that was moved. The game ends when one player, on their turn, is unable to move, and then that player loses.

We say a stone is matching if it has the same color as the square it occupies on the underlying checkerboard; otherwise it is clashing. In a checkerboard configuration, all stones are matching, i.e., the white stones occupy white squares and the black stones occupy black squares. And in a rectangular configuration, the stones occupy exactly the squares of some rectangular region on the board. Usually, Clobber starts from a rectangular checkerboard configuration, and White moves first (if the total number of stones is odd we assume that it is White who has one stone less than Black).

At the recent Dagstuhl Seminar on Algorithmic Combinatorial Game Theory , the game was first introduced to a broader audience. Tomáš Tichý from Prague won the first Clobber tournament, played on a $`5\times 6`$ board, beating his supervisor Jiří Sgall in the finals. Not much is known about Clobber strategies, even for small boards, and the computation of CGT game values is also only in its preliminary stages.

In this paper we introduce Solitaire Clobber, where a single player (or two cooperative players) tries to remove as many stones as possible from the board by alternating white and black moves. If the configuration ends up with $`k`$ immovable stones, we say that the initial board configuration is reduced to $`k`$ stones, or $`k`$-reduced. Obviously, 1-reducibility can only be possible if half of the stones are white (rounded down), and half of the stones are black (rounded up). But even then it might not be possible.

We prove the following necessary condition for a Clobber position to be 1-reducible: The number of stones plus the number of clashing stones cannot be a multiple of three. Surprisingly, this condition is also sufficient for truly two-dimensional rectangular checkerboard configurations (i.e., with at least two rows and two columns). And if the condition is not true, then the board is 2-reducible (with the last two stones separated by a single empty square), which is the next-best possible. However, in general, we show that it is NP-complete to decide whether an arbitrary (non-rectangular non-checkerboard) configuration is 1-reducible.

In one-dimensional Solitaire Clobber (i.e., the board consists of a single row of stones) we can usually not expect 1-reducibility. We show that the checkerboard configuration can be reduced to $`n/4+\{1\text{ if }n3(\mathrm{mod}4)\}`$ stones, no matter who moves first, and that this bound is best possible even if we do not have to alternate between white and black moves. This result was obtained independently by Grossman .

This paper is organized as follows. In Section 2, we analyze the reducibility of one-dimensional checkerboard configurations. In Section 3, we study reducibility of truly two-dimensional rectangular checkerboard configurations. And in Section 4 we show that deciding 1-reducibility is NP-complete for general configurations. We conclude with some open problems in Section 5.

## 2 One-Dimensional Solitaire Clobber

In this section we study Solitaire Clobber played on a board consisting of a single row of stones. Let $`A_n`$ denote the checkerboard configuration, i.e., an alternating sequence of white and black stones. By symmetry, we can assume throughout this section that $`A_n`$ always starts with a black stone, so we have $`A_n=\mathrm{}`$. We first show an upper bound on the $`k`$-reducibility of checkerboard configurations.

###### Theorem 1

For $`n1`$, the configuration $`A_n`$ can be reduced to $`n/4+\{1\text{ if }n3(\mathrm{mod}4)\}`$ stones by an alternating sequence of moves, no matter who is to move first.

Proof:  Split the configuration $`A_n`$ into $`n/4`$ substrings, all but possibly one of length four. Each substring of length one, two, or four can be reduced to one stone by alternating moves, no matter which color moves first. And a substring of size three can be reduced to two stones by one move, no matter which color moves first. $`\mathrm{}`$

In this move sequence, we end up with one isolated stone somewhere in the middle of each block of four consecutive stones. One might wonder whether a more clever strategy could end up with one stone at the end of each subblock, and then we could clobber one more stone in each pair of adjacent stones from the subblocks. Unfortunately, this is not possible, as shown by the following matching lower bound. The lower bound holds even if we are not forced to alternate between white and black moves. We give a simple proof for the theorem due to Grossman .

###### Theorem 2

Let $`n1`$. Even if we are not restricted to alternating white and black moves, the configuration $`A_n`$ cannot be reduced to fewer than $`n/4+\{1\text{ if }n3(\mathrm{mod}4)\}`$ stones.

Proof:  First, it is not possible to reduce $`A_k`$ to a single stone, for $`k=3`$ or $`k5`$. Second, each stone in the final configuration comes from some contiguous substring of stones in the initial configuration. But each of these substrings can have only one, two, or four stones. Thus, there are at least $`n/4`$ stones left at the end, and even one more if $`n3(\mathrm{mod}4)`$. $`\mathrm{}`$

Somewhat surprisingly, the tight bound of Theorems 1 and 2 is not monotone in $`n`$, the number of stones in the initial configuration. See Table 1.

## 3 Rectangular Solitaire Clobber

In this section we study reducibility of rectangular checkerboard configurations with at least two rows and two columns. We first show a general lower bound on the reducibility that holds for arbitrary Clobber configurations. For a configuration $`C`$, we denote the quantity “number of stones plus number of clashing stones” by $`\delta (C)`$.

As it turns out, $`\delta (C)(\mathrm{mod}3)`$ actually divides all clobber configurations into three equivalence classes. Any configuration will stay in the same equivalence class, after any number of moves. Because one of the three equivalence classes (with $`\delta (C)0(\mathrm{mod}3)`$) does not contain configurations with a single stone, all configurations in this equivalence class are not 1-reducible. As in the 1-dimensional lower bound of Theorem 2, this is true even if we allow arbitrary non-alternating move sequences.

###### Theorem 3

For a configuration $`C`$, $`\delta (C)(\mathrm{mod}3)`$ does not change after an arbitrary move sequence.

Proof:  If we move a matching stone in $`C`$ then $`\delta `$ drops by one because we clobber another matching stone, and $`\delta `$ rises by one because our stone becomes clashing, so $`\delta `$ actually does not change in this move. If we move a clashing stone then $`\delta `$ drops by two because we clobber another clashing stone, and $`\delta `$ drops by another one because our stone becomes matching, resulting in a total drop of three for the move. $`\mathrm{}`$

###### Corollary 4

A configuration $`C`$ with $`\delta (C)0(\mathrm{mod}3)`$ is not 1-reducible.

Proof:  A single stone can only have $`\delta `$ equal to one or two (depending on whether it is a matching or clashing stone). Thus, by the previous theorem, configurations $`C`$ with $`\delta (C)0(\mathrm{mod}3)`$ are not 1-reducible. $`\mathrm{}`$

The rest of this section is devoted to a proof that this bound is actually tight for rectangular checkerboard configurations:

###### Theorem 5

For $`n,m2`$, a rectangular checkerboard configuration with $`n`$ rows and $`m`$ columns is 2-reducible if $`nm0(\mathrm{mod}3)`$, and 1-reducible otherwise.

We present an algorithm that computes a sequence of moves that reduces the given checkerboard configuration to one or two stones as appropriate.

We distinguish cases in a somewhat complicated way. There are finitely many cases with $`2n,m6`$; these cases can be verified trivially, as shown in Appendix A. The remaining cases have at least one dimension with at least seven stones; by symmetry, we ensure that the configuration has at least seven columns. These cases we distinguish based on the parities of $`n`$ and $`m`$:

* Case EE: Even number of rows and columns \[Section 3.2\]
* Case OE: Odd number of rows, even number of columns \[Section 3.3\]
* Case EO: Even number of rows, odd number of columns \[Section 3.4\]
* Case OO: Odd number of rows and columns \[Section 3.4\]

Cases OE and EO are symmetric for configurations with at least seven rows and at least seven columns. By convention, we handle such situations in Case EO. But when one dimension is smaller than seven, we require that dimension to be rows, forcing us into Case OE or Case EO and breaking the symmetry. In fact, we solve these instances of Case OE by rotating the board and solving the simpler cases E3 and E5 (even number of rows, and three or five columns, respectively).

Section 3.1 gives an overview of our general approach. Section 3.2 considers Case EE, which serves as a representative example of the procedure. Section 3.3 extends this reduction to Case OE (when the number of rows is less than seven), which is also straightforward. Finally, Section 3.4 considers the remaining more-tedious cases in which the number of columns is odd.

### 3.1 General Approach

In each case, we follow the same basic strategy. We eliminate the stones on the board from top to bottom, two rows at a time. More precisely, each *step* reduces the topmost two rows down to $`O(1)`$ stones (usually one or two) arranged in a fixed pattern that touches the rest of the configuration through the bottom row.

There are usually four types of steps, repeated in the order

$$(1),\underset{}{(2),(3),(4)},\underset{}{(2),(3),(4)},\underset{}{(2),(3),(4)},\mathrm{}.$$

Step (1) leaves a small remainder of stones from the top two rows in a fixed pattern. Step (2) absorbs this remainder and the next two rows, in total reducing the top four rows down to a different pattern of remainder stones. Step (3) leaves yet another pattern of remainder stones from the top six rows. Finally, step (4) leaves the same pattern of remainder stones from step (1), so the sequence can repeat (2), (3), (4), (2), (3), (4), ….

In some simple cases, steps (1) and (2) leave the same pattern of remainder stones. Then just two types of steps suffice, repeating in the order $`(1),(2),(2),(2),\mathrm{}`$. In other cases, three steps suffice.

In any case, the step sequence may terminate with any type of step. Thus, we must also show how to reduce each pattern of remainder stones down to one or two stones as appropriate; when needed, these final reductions are enclosed by parentheses because they are only used at the very end. In addition, if the total number of rows is odd, the final step involves three rows instead of two rows, and must be treated specially.

In the description below, a single move is denoted by $``$ . But we often do not show long move sequences completely. Instead, we usually ‘jump’ several moves at a time, denoted by $`\stackrel{a}{}`$ or $`\underset{a}{}`$ , depending on whether White or Black moves first, where $`a`$ denotes the number of moves we jump.

### 3.2 Case EE: Even Number of Rows and Columns

We begin with the case in which both $`n`$ and $`m`$ are even. This case is easier than the other cases: the details are fairly clean. It serves as a representative example of the general approach.

Because the number of columns is even and at least seven, it must be at least eight. Every step begins by reducing the two involved rows down to a small number of columns. First, we clobber a few stones to create the following configuration in which the lower row has two more stones than the upper row, one on each side:

$``$$``$ $``$$``$ $`\mathrm{}`$  $``$$``$ $``$$``$ $`\stackrel{3}{}`$ $``$$``$ $``$$``$ $`\mathrm{}`$    .   .  $``$  .  $`\underset{3}{}`$   .   .    . $``$ $`\mathrm{}`$    .   .  $``$  .

Then we repeatedly apply the following reduction, in each step removing six columns, three on each side:

. $``$$``$$``$ $``$$``$$``$$``$ $`\mathrm{}`$  $``$$``$$``$  .  $``$$``$$``$$``$ $`\stackrel{4}{}`$   . $``$  . $``$   . $``$$``$$``$ $`\mathrm{}`$  $``$  . $``$  .  $``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   . $``$   .   . $``$$``$ $`\mathrm{}`$  $``$  .   .   .  $``$$``$  .   .  $`\stackrel{2}{}`$   .   .   .   .    .   .   . $``$ $`\mathrm{}`$    .   .   .   .  $``$  .   .   .

We stop applying this reduction when the bottom row has just six, eight, or ten columns left, and the top row has four, six, or eight columns, depending on whether $`m2`$, $`1`$, or $`0(\mathrm{mod}3)`$, respectively.

The resulting two-row configuration has either a black stone in the lower-left and a white stone in the lower-right corner (

.

.

)

.

.

\Big{(}\vbox{\hbox{\ignorespaces\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}$\bullet$}\vskip-6.0pt\hbox{\ignorespaces$\bullet$$\circ$}}\cdots\vbox{\hbox{\ignorespaces$\circ$\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}}\vskip-6.0pt\hbox{\ignorespaces$\bullet$$\circ$}}\Big{)}, or vice versa (

.

.

)

.

.

\Big{(}\vbox{\hbox{\ignorespaces\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}$\circ$}\vskip-6.0pt\hbox{\ignorespaces$\circ$$\bullet$}}\cdots\vbox{\hbox{\ignorespaces$\bullet$\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}}\vskip-6.0pt\hbox{\ignorespaces$\circ$$\bullet$}}\Big{)}. We show reductions for the former case; the latter case is symmetric.

#### Case 1: $`m2(\mathrm{mod}3)`$

* . $``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$ $`\stackrel{3}{}`$   .   .   . $``$$``$  .    . $``$$``$$``$$``$$``$ $`\underset{3}{}`$   .   .   .   .   .   .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   . $``$$``$  .   .  $`(`$ $``$   .   .   .   .   .   .    .   .   . $``$  .   .  $`)`$111Parenthetical moves are made only if this is the final step.
* .   . $``$$``$  .   .    . $``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$  .   .   .    . $``$$``$$``$  .   .  $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$  .   .   .    .   . $``$$``$  .   .  $``$$``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   . $``$$``$  .   .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    . $``$$``$$``$$``$  .  $`\stackrel{3}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    .   . $``$  .   .   .
* .   . $``$  .   .   .    . $``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$ $`\underset{2}{}`$   .   . $``$  .   .   .    . $``$$``$$``$$``$  .    . $``$$``$$``$$``$  .  $`\underset{2}{}`$   .   .   .   .   .   .    .   . $``$$``$$``$  .    . $``$$``$$``$$``$  .  $`\underset{2}{}`$   .   .   .   .   .   .    .   .   .   . $``$  .    . $``$$``$$``$$``$  .  $`\underset{1}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    . $``$  . $``$  .   .
* . $``$  . $``$  .   .    . $``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  .   .   .   .    . $``$  . $``$$``$  .  $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .    . $``$  .   . $``$  .  $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .    . $``$  .   . $``$  .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    .   . $``$$``$  .   .  $`(`$ $``$   .   .   .   .   .   .    .   .   .   .   .   .    .   .   . $``$  .   .  $`)`$

#### Case 2: $`m1(\mathrm{mod}3)`$

* First we clear another six columns and obtain

. $``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{12}{}`$   .   .   .   .   .   .   .   .    .   .   . $``$$``$  .   .   .  $``$   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .
* .   .   .   . $``$  .   .   .    . $``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$ $`\underset{3}{}`$   .   .   .   . $``$  .   .   .    . $``$$``$$``$$``$  .   .   .  $``$$``$$``$$``$$``$$``$$``$  .  $`\stackrel{3}{}`$   .   .   .   . $``$  .   .   .    .   .   . $``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$  .  $`\underset{2}{}`$   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .    . $``$$``$$``$$``$$``$$``$  .  $`\underset{2}{}`$   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .    . $``$$``$$``$$``$$``$  .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .    .   .   . $``$  .   .   .   .
* .   .   . $``$  .   .   .   .    . $``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$ $`\underset{3}{}`$   .   .   . $``$  .   .   .   .    . $``$$``$$``$$``$  .   .   .  $``$$``$$``$$``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   . $``$  .   .   .   .    . $``$  . $``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   . $``$  .   .   .   .    .   .   . $``$$``$  .   .   .    . $``$$``$$``$$``$$``$  .   .  $`\stackrel{2}{}`$   .   .   . $``$  .   .   .   .    .   .   . $``$  .   .   .   .    . $``$$``$$``$$``$  .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .    . $``$  . $``$  .   .   .   .
* . $``$  . $``$  .   .   .   .    . $``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  . $``$  .   .   .   .    . $``$$``$$``$$``$  . $``$  .  $``$$``$$``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   . $``$  .   .   .   .    .   . $``$$``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .   .   .    .   .   . $``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .    .   .   . $``$$``$$``$  .   .  $`\stackrel{3}{}`$   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .

#### Case 3: $`m0(\mathrm{mod}3)`$

* First we clear another six columns and obtain

. $``$$``$$``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{12}{}`$   .   .   .   . $``$$``$  .   .   .   .    .   .   . $``$$``$$``$$``$  .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .   .    .   .   . $``$  . $``$  .   .   .   .
* .   .   . $``$  . $``$  .   .   .   .    . $``$$``$$``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{6}{}`$   .   .   . $``$  . $``$  .   .   .   .    .   .   . $``$$``$$``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   . $``$  .   .   .   .   .   .    .   .   . $``$$``$  . $``$  .   .   .    .   . $``$$``$$``$  . $``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .   .    .   . $``$$``$$``$  . $``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .   .    .   .   .   . $``$  . $``$  .   .   .
* .   .   .   . $``$  . $``$  .   .   .    . $``$$``$$``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{6}{}`$   .   .   .   . $``$  . $``$  .   .   .    .   .   . $``$$``$$``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   .   .   .   . $``$  .   .   .    .   .   .   . $``$$``$$``$  .   .   .    .   . $``$$``$$``$$``$$``$$``$  .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .   .    .   .   .   .   .   . $``$  .   .   .    .   . $``$$``$  . $``$$``$$``$  .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .   .    .   .   . $``$  . $``$  .   .   .   .

### 3.3 Case OE: Odd Number of Rows, Even Number of Columns

To extend Case EE from the previous section to handle an odd number of rows, we could provide extra termination cases with three instead of two rows for any step. Because these steps are always final, they may produce an arbitrary result configuration with one or two stones.

However, as observed before, we only need to consider configurations with three or five rows in Case OE (any other configuration can be rotated into a Case EO). It turns out that we can describe their reduction more easily (and conform with all other cases) by first rotating them. Thus, the following reductions use the general approach from Section 3.1 to reduce configurations with three or five columns and an even number of rows.

#### Three Columns:

* $``$$``$$``$ $``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$ $``$$``$$``$ $`\stackrel{2}{}`$   .   .   .  $``$  . $``$
* $``$  . $``$ $``$$``$$``$ $``$$``$$``$ $`\stackrel{2}{}`$ $``$  .   .  $``$  . $``$ $``$$``$$``$ $`\stackrel{2}{}`$   .   .   .  $``$  . $``$ $``$  . $``$ $`\stackrel{2}{}`$   .   .   .    .   .   .  $``$  . $``$

#### Five Columns:

* $``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$$``$$``$$``$   . $``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$$``$$``$  .    . $``$$``$$``$  .  $`\stackrel{2}{}`$   . $``$$``$  .   .    .   . $``$$``$  .  $`\stackrel{3}{}`$   .   .   .   .   .    .   . $``$  .   .
* .   . $``$  .   .  $``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$ $`\underset{4}{}`$   .   . $``$  .   .    . $``$$``$$``$  .    . $``$$``$$``$  .  $`\underset{3}{}`$   .   .   .   .   .    . $``$$``$  .   .    . $``$$``$  .   .  $`\stackrel{3}{}`$   .   .   .   .   .    .   .   .   .   .    . $``$  .   .   .
* . $``$  .   .   .  $``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$ $`\underset{4}{}`$   . $``$  .   .   .    . $``$$``$$``$  .    . $``$$``$$``$  .  $`\underset{3}{}`$   .   .   .   .   .    . $``$  . $``$  .    . $``$  . $``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    .   .   .   .   .    . $``$  . $``$  .
* . $``$  . $``$  .  $``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   . $``$  .   .   .    . $``$$``$$``$$``$   . $``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    . $``$  . $``$$``$   . $``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    .   .   . $``$  .    . $``$$``$$``$  .  $`\stackrel{3}{}`$   .   .   .   .   .    .   .   .   .   .    .   . $``$  .   .

### 3.4 Cases EO and OO: Odd Number of Columns

Finally we consider the case of an even or odd number of rows and an odd number of columns. For each step, we give two variants, one reduction from two rows and one reduction from three rows. The latter case is applied only at the end of the reduction, so it does not need to end with the same pattern of remainder stones. Also, for an odd number of rows, the initial symmetrical removal of columns from both ends of the rows in a step is done first for the final three-row step, before any other reduction; this order is necessary because the three-row symmetrical removal can start only with a White move.

The number of columns is at least seven. Every step begins by reducing the two or three involved rows down to a small number of columns.

#### Two Rows.

First, we clobber a few stones to create the following configuration in which the upper row has one more stone on the left side than the lower row, and the lower row has one more stone on the right side than the upper row:

$``$$``$ $``$$``$ $`\mathrm{}`$  $``$$``$ $``$$``$ $`\stackrel{3}{}`$   . $``$   .   .  $`\mathrm{}`$  $``$$``$ $``$$``$ $`\underset{3}{}`$   . $``$   .   .  $`\mathrm{}`$    .   .  $``$  .

Similar to Case EE, we repeatedly apply the following reduction, in each step removing six columns, three on each side:

$``$$``$$``$$``$   . $``$$``$$``$ $`\mathrm{}`$  $``$$``$$``$  .  $``$$``$$``$$``$ $`\stackrel{3}{}`$ $``$$``$$``$$``$   . $``$$``$$``$ $`\mathrm{}`$  $``$  .   .   .  $``$$``$$``$  .  $`\underset{3}{}`$   . $``$$``$$``$   .   .   . $``$ $`\mathrm{}`$  $``$  .   .   .  $``$$``$$``$  .  $`\stackrel{2}{}`$   .   . $``$$``$   .   .   . $``$ $`\mathrm{}`$  $``$  .   .   .  $``$$``$  .   .  $`\stackrel{4}{}`$   .   .   . $``$   .   .   .   .  $`\mathrm{}`$    .   .   .   .  $``$  .   .   .

We stop applying this reduction when the total number of columns is just five, seven, or nine, so each row has four, six, or eight occupied columns, depending on whether $`m1`$, $`0`$, or $`2(\mathrm{mod}3)`$, respectively.

The resulting two-row configuration has either (a) a black stone in the upper-left and a white stone in the lower-right corner (

.

.

)

.

.

\Big{(}\vbox{\hbox{\ignorespaces$\bullet$$\circ$$\bullet$}\vskip-6.0pt\hbox{\ignorespaces\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}$\bullet$$\circ$}}\cdots\vbox{\hbox{\ignorespaces$\bullet$$\circ$\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}}\vskip-6.0pt\hbox{\ignorespaces$\circ$$\bullet$$\circ$}}\Big{)}, or (b) vice versa (

.

.

)

.

.

\Big{(}\vbox{\hbox{\ignorespaces$\circ$$\bullet$$\circ$}\vskip-6.0pt\hbox{\ignorespaces\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}$\circ$$\bullet$}}\cdots\vbox{\hbox{\ignorespaces$\circ$$\bullet$\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}}\vskip-6.0pt\hbox{\ignorespaces$\bullet$$\circ$$\bullet$}}\Big{)}. We will show reductions from both configurations. It turns out that configuration (a) is more difficult to handle because it is not always possible to end up with a single stone (or pair of stones) on the bottom row. In that case, we will make the last move parenthetical, omitting it whenever this step is not the last.

Sometimes we also need to start from the configuration (a)

.

.

.

.

\vbox{\hbox{\ignorespaces\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}$\circ$$\bullet$}\vskip-6.0pt\hbox{\ignorespaces$\circ$$\bullet$$\circ$}}\cdots\vbox{\hbox{\ignorespaces$\bullet$$\circ$$\bullet$}\vskip-6.0pt\hbox{\ignorespaces$\circ$$\bullet$\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}}} or (b)

.

.

.

.

\vbox{\hbox{\ignorespaces\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}$\bullet$$\circ$}\vskip-6.0pt\hbox{\ignorespaces$\bullet$$\circ$$\bullet$}}\cdots\vbox{\hbox{\ignorespaces$\circ$$\bullet$$\circ$}\vskip-6.0pt\hbox{\ignorespaces$\bullet$$\circ$\parbox[c][4.44444pt]{5.00002pt}{\centering.\@add@centering}}} which are the mirror images of the configurations (a) and (b). These starting points can be achieved by applying the reductions above upside-down.

#### Three rows.

First, we clobber a few stones to create the following configuration:

$``$$``$ $``$$``$ $``$$``$ $`\mathrm{}`$  $``$$``$ $``$$``$ $``$$``$ $`\stackrel{8}{}`$   . $``$   .   .    . $``$ $`\mathrm{}`$  $``$  .    .   .  $``$  .

Then, we reduce long rows by four columns at a time (not six as in the two-row reductions):

$``$$``$$``$   . $``$$``$ $``$$``$$``$ $`\mathrm{}`$  $``$$``$$``$ $``$$``$  .  $``$$``$$``$ $`\stackrel{3}{}`$   . $``$$``$   .   . $``$   . $``$$``$ $`\mathrm{}`$  $``$$``$$``$ $``$$``$  .  $``$$``$$``$ $`\underset{3}{}`$   .   . $``$   .   .   .    .   . $``$ $`\mathrm{}`$  $``$$``$$``$ $``$$``$  .  $``$$``$$``$ $`\stackrel{3}{}`$   .   . $``$   .   .   .    .   . $``$ $`\mathrm{}`$  $``$$``$  .  $``$  .   .  $``$$``$  .  $`\underset{3}{}`$   .   . $``$   .   .   .    .   . $``$ $`\mathrm{}`$  $``$  .   .    .   .   .  $``$  .   .

Note that we can also obtain the symmetric configuration    .   . $``$   .   .   .    .   . $``$ $`\mathrm{}`$  $``$  .   .    .   .   .  $``$  .   .  . Because we cannot perform this reduction with Black starting, we must perform this reduction at the very beginning of the entire algorithm, before any other steps.

We stop this reduction when we have reached one of the three configurations  $``$$``$$``$   . $``$  .  $``$$``$$``$  or  $``$$``$$``$$``$$``$   . $``$$``$$``$  .  $``$$``$$``$$``$$``$  or  $``$$``$$``$$``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$ . The last configuration could be reduced further but in some cases that would isolate the remaining stones from the remainder stones of the rows above.

#### Reductions.

Now we show how to reduce the configurations described above following the general approach from Section 3.1. For the case of three rows, we only need to consider the following two reductions in step (1):

* $``$$``$$``$   . $``$  .  $``$$``$$``$ $`\stackrel{2}{}`$ $``$$``$$``$   . $``$  .    . $``$  .  $`\stackrel{3}{}`$   . $``$  .    .   .   .    . $``$  .
* $``$$``$$``$$``$$``$   . $``$$``$$``$  .  $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  . $``$$``$   . $``$$``$$``$  .  $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  . $``$  .    . $``$  . $``$  .  $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    . $``$  . $``$  .  $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   . $``$  .    . $``$$``$$``$$``$ $`\stackrel{3}{}`$   .   .   .   .   .    .   .   .   .   .    . $``$  . $``$  .

#### Case 1: $`m1(\mathrm{mod}3)`$

The initial configuration is of type (a) for $`m=13+12k`$ columns and of type (b) for $`m=7+12k`$ columns, for $`k0`$.

* $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$ $``$$``$$``$$``$  .    .   . $``$$``$  .  $`\stackrel{2}{}`$   . $``$$``$  .   .    .   . $``$$``$  .  $`\stackrel{2}{}`$   .   . $``$  .   .    .   . $``$  .   .  $`(`$ $``$   .   . $``$  .   .    .   .   .   .   .  $`)`$
* $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$$``$  .   .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$  .   .    . $``$$``$$``$  .  $`\stackrel{3}{}`$   .   .   .   .   .    .   . $``$  .   .
* .   . $``$  .   .    .   . $``$  .   .  $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$  .   .    .   . $``$  .   .    . $``$$``$$``$  .    . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   . $``$  .   .    . $``$$``$$``$  .    .   .   . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   .   .   .    .   . $``$$``$  .    .   .   . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   .   .   .    .   .   . $``$  .    .   .   . $``$  .  $`(`$ $``$   .   .   .   .   .    .   .   .   .   .    .   .   . $``$  .    .   .   .   .   .  $`)`$

.   .   . $``$  .   .   .    .   .   . $``$  .   .   .  $``$$``$$``$$``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   .   .   . $``$  .   .   .    .   .   . $``$  .   .   .    .   .   . $``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   .   .   . $``$  .   .   .    .   .   . $``$  .   .   .    .   .   . $``$$``$$``$$``$   .   . $``$$``$$``$$``$  .    .   .   .   . $``$$``$$``$ $`\stackrel{4}{}`$   .   .   . $``$  .   .   .    .   .   . $``$  .   .   .    .   .   . $``$$``$$``$  .    .   . $``$$``$$``$$``$  .    .   .   .   .   .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .    .   .   . $``$  .   .   .    .   .   . $``$$``$  .   .    .   .   . $``$$``$  .   .    .   .   .   .   .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .    .   .   .   .   .   .   .    .   .   .   .   .   .   .    .   .   . $``$  .   .   .    .   .   .   .   .   .   .
* .   . $``$  .   .  $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\underset{3}{}`$   .   .   .   .   .  $``$$``$$``$  .   .    . $``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .  $``$$``$  .   .   .    . $``$$``$  .   .  $`\stackrel{3}{}`$   .   .   .   .   .    .   .   .   .   .    . $``$  .   .   .

.   . $``$  .   .  $``$$``$$``$$``$$``$   . $``$$``$$``$  .  $``$$``$$``$$``$$``$ $`\underset{4}{}`$   .   . $``$  .   .  $``$$``$$``$$``$$``$   . $``$  . $``$  .    . $``$  . $``$  .  $`\underset{4}{}`$   .   . $``$  .   .  $``$$``$$``$$``$  .    . $``$  .   .   .    .   .   .   .   .  $`\stackrel{5}{}`$   .   .   .   .   .    .   . $``$  .   .    .   .   .   .   .    .   .   .   .   .
* .   .   . $``$  .    .   .   . $``$  .  $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   . $``$  .    .   .   . $``$  .    . $``$$``$$``$  .    . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   . $``$  .    . $``$  . $``$  .    . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   .   .   .    .   .   . $``$  .    . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   .   .   .    .   .   .   .   .    . $``$  . $``$  .

.   .   .   . $``$  .   .    .   .   .   . $``$  .   .  $``$$``$$``$$``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   .   .   .   . $``$  .   .    .   .   .   . $``$  .   .    .   .   . $``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   .   .   .   . $``$  .   .    .   .   .   . $``$  .   .    .   .   . $``$$``$$``$$``$   .   . $``$$``$$``$$``$  .    .   .   .   . $``$$``$$``$ $`\stackrel{4}{}`$   .   .   .   . $``$  .   .    .   .   .   . $``$  .   .    .   .   . $``$$``$$``$  .    .   . $``$$``$$``$$``$  .    .   .   .   .   .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .    .   .   .   . $``$  .   .    .   .   . $``$$``$  .   .    .   .   . $``$$``$  .   .    .   .   .   .   .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .    .   .   .   .   .   .   .    .   .   . $``$  .   .   .    .   .   .   .   .   .   .    .   .   .   .   .   .   .
* . $``$  .   .   .  $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\underset{3}{}`$   .   .   .   .   .  $``$$``$  .   .   .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    . $``$  .   .   .    . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .    .   .   .   .   .    . $``$  . $``$  .

. $``$  .   .   .  $``$$``$$``$$``$$``$   . $``$$``$$``$  .  $``$$``$$``$$``$$``$ $`\underset{4}{}`$   . $``$  .   .   .  $``$$``$$``$$``$$``$   . $``$  . $``$  .    . $``$  . $``$  .  $`\underset{4}{}`$   . $``$  .   .   .  $``$$``$$``$$``$  .    . $``$  .   .   .    .   .   .   .   .  $`\underset{5}{}`$   .   .   .   .   .    . $``$  .   .   .    .   .   .   .   .    .   .   .   .   .
* . $``$  . $``$  .  $``$$``$$``$$``$  .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  . $``$  .    . $``$$``$$``$  .    . $``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    . $``$$``$$``$  .    . $``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    .   . $``$$``$  .    .   . $``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    .   . $``$  .   .    .   . $``$  .   .  $`(`$ $``$   .   .   .   .   .    .   . $``$  .   .    .   .   .   .   .  $`)`$

$``$  . $``$ $``$$``$$``$   . $``$  .  $``$$``$$``$ $`\stackrel{2}{}`$   .   .   .  $``$$``$$``$   . $``$  .  $``$$``$$``$ $`\stackrel{2}{}`$   .   .   .    . $``$  .    . $``$  .  $``$$``$$``$ $`\stackrel{3}{}`$   .   .   .    . $``$  .    .   .   .    . $``$  .
* In the two-rows case, we must reduce rows seven and eight starting with the mirrored standard initial configuration.

. $``$  . $``$  .    . $``$$``$$``$$``$ $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   . $``$  .   .   .    . $``$$``$$``$  .  $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   . $``$  .   .   .    . $``$  . $``$  .    . $``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .    . $``$  .   .   .    . $``$$``$$``$  .  $`\stackrel{3}{}`$   .   .   .   .   .    .   .   .   .   .    .   . $``$  .   .

. $``$  . $``$  .  $``$$``$$``$$``$$``$   . $``$$``$$``$  .  $``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   . $``$  . $``$  .  $``$$``$$``$$``$$``$   . $``$  . $``$  .    . $``$  . $``$  .  $`\stackrel{4}{}`$   . $``$  . $``$  .  $``$$``$$``$$``$  .    . $``$  .   .   .    .   .   .   .   .  $`\stackrel{5}{}`$   .   .   .   .   .    . $``$  . $``$  .    .   .   .   .   .    .   .   .   .   .

#### Case 2: $`m0(\mathrm{mod}3)`$

The initial configuration is of type (a) for $`m=15+12k`$ columns and of type (b) for $`m=9+12k`$ columns, for $`k0`$.

* $``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$$``$  . $``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  .   . $``$$``$  .    . $``$$``$  . $``$$``$$``$ $`\stackrel{2}{}`$   . $``$  .   .   . $``$  .    . $``$$``$  . $``$$``$  .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .    .   . $``$  . $``$  .   .
* $``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$$``$  . $``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$  .   . $``$$``$  .    . $``$$``$  . $``$$``$$``$ $`\stackrel{2}{}`$   . $``$  .   .   . $``$  .    . $``$$``$  . $``$$``$  .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .    .   . $``$  . $``$  .   .
* .   . $``$  . $``$  .   .  $``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$  . $``$  .   .    . $``$$``$$``$$``$  .   .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   . $``$  .   .    .   . $``$  . $``$  .   .    .   . $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .   .    .   .   .   . $``$  .   .    .   . $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .   .    .   .   .   . $``$  .   .    .   . $``$  . $``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .   .    .   .   .   .   .   .   .    .   . $``$  . $``$  .   .

For three rows, this case is identical to Case 1(4b).
* .   . $``$  . $``$  .   .  $``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   . $``$  .   .    . $``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   . $``$  .   .    . $``$$``$  . $``$$``$  .    . $``$$``$  . $``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .   .    . $``$  .   . $``$$``$  .    . $``$$``$  . $``$$``$$``$ $`\stackrel{6}{}`$   .   .   .   .   .   .   .    .   .   .   .   .   .   .    .   . $``$  . $``$  .   .

For three rows, this case is symmetric to (4a) in Case 1 (with the mirrored initial configuration).

#### Case 3: $`m2(\mathrm{mod}3)`$

The initial configuration is of type (a) for $`m=17+12k`$ columns and of type (b) for $`m=11+12k`$ columns, for $`k0`$.

* $``$$``$$``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   . $``$$``$$``$$``$$``$  . $``$  .    . $``$  . $``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   . $``$$``$$``$$``$  .   .   .    .   .   .   . $``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   . $``$$``$  .   .   .   .    .   .   .   . $``$$``$  .   .   .  $`\stackrel{3}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .   .
* $``$$``$$``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   . $``$$``$$``$$``$$``$  . $``$  .    . $``$  . $``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   . $``$$``$$``$$``$  .   .   .    .   .   . $``$$``$$``$$``$  .   .  $`\stackrel{4}{}`$   .   .   . $``$  .   .   .   .   .    .   .   . $``$$``$$``$  .   .   .  $`\stackrel{3}{}`$   .   .   .   .   .   .   .   .   .    .   .   . $``$  .   .   .   .   .
* .   .   .   . $``$  .   .   .   .  $``$$``$$``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$$``$$``$ $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .  $``$$``$$``$$``$$``$$``$  .   .   .    . $``$$``$$``$$``$$``$$``$$``$  .  $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .  $``$$``$$``$$``$$``$$``$  .   .   .    . $``$  . $``$  . $``$  .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .    .   . $``$$``$$``$$``$  .   .   .    .   .   . $``$  .   .   .   .   .  $`(`$ $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .   .    .   .   .   .   .   .   .   .   .  $`)`$

.   .   . $``$  .   .   .  $``$$``$$``$$``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$ $`\underset{4}{}`$   .   .   . $``$  .   .   .    . $``$  . $``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .  $``$$``$$``$  .   . $``$$``$ $`\underset{4}{}`$   .   .   . $``$  .   .   .    .   .   . $``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .    .   . $``$  .   . $``$  .  $`\underset{4}{}`$   .   .   . $``$  .   .   .    .   .   . $``$$``$$``$  .    .   . $``$$``$$``$$``$  .    .   .   .   .   .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .    .   .   .   . $``$  .   .    .   . $``$$``$$``$  .   .    .   .   .   .   .   .   .  $`\underset{3}{}`$   .   .   .   .   .   .   .    .   .   .   .   .   .   .    .   .   .   . $``$  .   .    .   .   .   .   .   .   .
* .   .   . $``$  .   .   .   .   .  $``$$``$$``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$$``$$``$ $`\underset{6}{}`$   .   .   . $``$  .   .   .   .   .    . $``$$``$$``$$``$$``$  .   .   .    .   .   . $``$$``$$``$$``$$``$  .  $`\underset{3}{}`$   .   .   . $``$  .   .   .   .   .    .   . $``$$``$$``$  .   .   .   .    .   .   . $``$$``$$``$$``$  .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .   .    .   .   .   . $``$$``$$``$  .   .  $`\stackrel{3}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .   .

For three rows, this case is identical to Case 1(3b).
* .   . $``$$``$$``$$``$  .   .   .    .   .   . $``$  .   .   .   .   .  $``$$``$$``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$$``$$``$ $`\underset{4}{}`$   .   . $``$$``$$``$  .   .   .   .    .   .   . $``$  .   .   .   .   .  $``$$``$$``$$``$$``$$``$$``$$``$  .    .   . $``$  .   . $``$$``$$``$$``$ $`\underset{4}{}`$   .   . $``$$``$$``$  .   .   .   .    .   .   . $``$  .   .   .   .   .    .   . $``$$``$$``$$``$$``$$``$  .    .   .   .   .   . $``$  . $``$$``$ $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   . $``$  .   .   .   .   .    .   .   . $``$$``$$``$$``$$``$  .    .   .   .   .   . $``$  . $``$$``$ $`\underset{6}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   .   .   . $``$  .   .   .    .   .   .   .   . $``$  .   . $``$  $`(`$$``$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   .   .   . $``$  .   .   .    .   .   .   .   .   .   .   . $``$  $`)`$

$``$$``$$``$$``$  .    . $``$  .   .    . $``$$``$$``$   .   . $``$  .    . $``$$``$$``$ $`\underset{4}{}`$   . $``$  .   .   .    . $``$  .   .    . $``$$``$$``$   .   . $``$  .    .   . $``$$``$ $`\underset{4}{}`$   .   .   .   .   .    . $``$  .   .    . $``$$``$  .    .   . $``$  .    .   .   .   .  $`\underset{3}{}`$   .   .   .   .   .    .   .   .   .    . $``$  .   .    .   .   .   .    .   .   .   .
* In the two-rows case, we must reduce rows five and six starting with the mirrored standard initial configuration (we could also solve the standard configuration, but then we could not continue with step (4b)).

.   .   .   . $``$  .   .   .   .    . $``$$``$$``$$``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$$``$$``$$``$  .  $`\underset{6}{}`$   .   .   .   . $``$  .   .   .   .    .   .   . $``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$  .   .   .  $`\underset{3}{}`$   .   .   .   . $``$  .   .   .   .    .   .   .   . $``$$``$$``$  .   .    .   . $``$$``$$``$$``$  .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   . $``$  .   .   .    .   . $``$$``$  . $``$  .   .   .  $`\stackrel{2}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   . $``$  . $``$  .   .   .

For three rows, this case is identical to Case 1(2b).
* In the two-rows case, we must reduce rows seven and eight starting with the mirrored standard initial configuration (because of the white single stone left over at the right end of row six).

.   .   .   .   . $``$  .   .   .    .   .   .   .   . $``$  .   . $``$   . $``$$``$$``$$``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$$``$$``$$``$  .  $`\underset{4}{}`$   .   .   .   .   . $``$  .   .   .    .   .   .   .   . $``$  .   .   .    . $``$$``$$``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$  . $``$  .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   . $``$  .   .   .    . $``$  . $``$$``$$``$$``$  .   .  $``$$``$$``$$``$$``$  .   .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   . $``$$``$$``$  .   .   .    . $``$$``$$``$$``$  .   .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .   .    .   .   . $``$$``$  .   .   .   .  $`\underset{2}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   .   . $``$  .   .   .   .

In the three-rows case, we must reduce the number of columns a little bit asymmetrically (remove four additional columns on the left side) and then do the following reduction.

.   . $``$  .   .   .   .    .   . $``$  .   . $``$  .  $``$$``$$``$$``$$``$$``$$``$   . $``$$``$$``$$``$$``$  .  $``$$``$$``$$``$$``$$``$$``$ $`\underset{4}{}`$   .   . $``$  .   .   .   .    .   . $``$  .   .   .   .  $``$$``$$``$$``$$``$$``$$``$   . $``$$``$$``$  . $``$  .  $``$$``$$``$$``$  . $``$  .  $`\underset{4}{}`$   .   .   .   .   .   .   .    .   . $``$  .   .   .   .  $``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$  .   .   .  $``$$``$$``$$``$  .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .    .   . $``$  .   .   .   .  $``$$``$$``$$``$$``$  .   .    . $``$$``$$``$  .   .   .    . $``$  .   .   .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .    .   . $``$  .   .   .   .  $``$$``$$``$$``$  .   .   .    .   . $``$  .   .   .   .    .   .   .   .   .   .   .  $`\underset{4}{}`$   .   .   .   .   .   .   .    .   .   .   .   .   .   .  $``$  . $``$  .   .   .   .    .   .   .   .   .   .   .    .   .   .   .   .   .   .
* .   .   . $``$  . $``$  .   .   .  $``$$``$$``$$``$$``$$``$$``$$``$  .    . $``$$``$$``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   .   .   . $``$  . $``$  .   .   .    . $``$$``$$``$  . $``$$``$$``$  .    .   .   . $``$$``$$``$$``$$``$$``$ $`\stackrel{4}{}`$   .   .   . $``$  .   .   .   .   .    . $``$$``$$``$  . $``$  .   .   .    .   .   . $``$$``$$``$$``$$``$  .  $`\stackrel{4}{}`$   .   .   . $``$  .   .   .   .   .    .   . $``$$``$  .   .   .   .   .    .   .   . $``$$``$$``$  .   .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .   .   .   .    .   .   .   .   .   .   .   .   .    .   .   . $``$  .   .   .   .   .

For three rows, this case is identical to Case 1(4b).

## 4 NP-Completeness of 1-Reducibility

In this section we consider arbitrary initial Clobber positions that do not need to have a rectangular shape or the alternating checkerboard placement of the stones. We show that then the following problem is NP-complete.

Problem Solitaire-Clobber: Given an arbitrary initial Clobber configuration, decide whether we can reduce it to a single stone.

The proof is by reduction from the Hamiltonian circuit problem in grid graphs. A grid graph is a finite graph embedded in the Euclidean plane such that the vertices have integer coordinates and two vertices are connected by an edge if and only if their Euclidean distance is equal to one.

Problem Grid-Hamiltonicity: Decide whether a given grid graph has a Hamiltonian circuit.

Itai et al. proved that Grid-Hamiltonicity is NP-complete \[3, Theorem 2.1\].

###### Theorem 6

Solitaire-Clobber is NP-complete.

Proof:  We first observe that Solitaire-Clobber is indeed in NP, because we can easily check in polynomial time whether a proposed solution (which must have only $`n1`$ moves) reduces the given initial configuration to a single stone.

We prove the NP-completeness by reduction from Grid-Hamiltonicity. Let $`G`$ be an arbitrary grid graph with $`n`$ nodes, embedded in the Euclidean plane. Let $`v`$ be a node of $`G`$ with maximum $`y`$-coordinate, and among all such nodes the node with maximum $`x`$-coordinate. If $`v`$ does not have a neighbor to the left then $`G`$ cannot have a Hamiltonian circuit. So assume there is a left neighbor $`w`$ of $`v`$. Note that $`v`$ has degree two and therefore any Hamiltonian circuit in $`G`$ must use the edge $`(v,w)`$.

Then we construct the following Clobber configuration (see Figure 1). We put a black stone on each node of $`G`$. We place a single white stone just above $`w`$, the bomb. We place a vertical chain of $`n`$ white stones above $`v`$, the fuse, and another single black stone, the fire, on top of the fuse. Altogether we have placed $`n+1`$ white and $`n+1`$ black stones, so this is a legal Clobber configuration.

If $`G`$ has a Hamiltonian circuit $`C`$ then the bomb can clobber all black nodes of $`G`$, following $`C`$ starting in $`w`$ and ending in $`v`$ after $`n`$ rounds. At the same time, the black fire can clobber the $`n`$ stones of the fuse and end up just above $`v`$ after $`n`$ rounds. But then in a last step the bomb can clobber the fire, leaving a single stone on the board.

On the other hand, if the initial configuration can be reduced to a single stone then White cannot move any stone on the fuse (because that would disconnect the black fire from the stones on $`G`$), so it must move the bomb until Black has clobbered the fuse. But that takes $`n`$ steps, so White must in the meanwhile clobber all $`n`$ black stones of $`G`$, that is, it must walk along a Hamiltonian circuit in $`G`$. $`\mathrm{}`$

## 5 Conclusions

We have seen that reducing a given Clobber configuration to the minimum number of stones is polynomially solvable for rectangular checkerboard configurations, and is NP-hard for general configurations. What about non-rectangular checkerboard configurations and rectangular non-checkerboard configurations?

We have also seen a lower bound on the number of stones to which a configuration can be reduced that is based on the number of stones plus the number of stones on squares of different color. It would be interesting to identify other structural parameters of a configuration that influence reducibility.

## Appendix A Small Cases

Our proof of Theorem 5 requires us to verify reducibility for all instances with $`2n,m6`$. This fact can be checked easily by a computer, but for completeness we give the reductions here. By symmetry, we only need to show the cases with $`nm`$. Reductions of $`2\times 3`$, $`2\times 5`$, $`3\times 4`$, $`3\times 6`$, $`4\times 5`$, and $`5\times 6`$ boards are already given in Section 3.3. Eight more small boards remain. We assume White moves first.

$``$$``$ $``$$``$ $``$ $``$  .  $``$$``$ $``$   .   .  $``$$``$ $``$   .   .  $``$  .

$``$$``$$``$$``$ $``$$``$$``$$``$ $``$ $``$$``$$``$  .  $``$$``$$``$$``$ $``$ $``$$``$  .   .  $``$$``$$``$$``$ $``$ $``$$``$  .   .  $``$$``$$``$  .  $``$   . $``$  .   .  $``$$``$$``$  .  $``$   .   .   .   .  $``$$``$$``$  .  $``$   .   .   .   .    . $``$$``$  .  $``$   .   .   .   .    . $``$  .   .

$``$$``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$$``$ $`\stackrel{3}{}`$ $``$$``$$``$$``$  .   .  $``$$``$$``$$``$$``$  .  $`\underset{3}{}`$   .   . $``$$``$  .   .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    . $``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .    .   . $``$  . $``$  .

$``$$``$$``$ $``$$``$$``$ $``$$``$$``$ $`\stackrel{2}{}`$ $``$  . $``$ $``$  . $``$ $``$$``$$``$ $`\stackrel{3}{}`$   .   .   .    .   .   .  $``$  . $``$

$``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$ $``$$``$$``$$``$$``$   .   . $``$$``$$``$ $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   . $``$$``$$``$$``$   .   . $``$$``$$``$   . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   . $``$$``$$``$   .   .   . $``$$``$   . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   . $``$$``$   .   .   . $``$  .    . $``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   . $``$  .    .   .   . $``$  .    . $``$$``$$``$  .  $`\stackrel{3}{}`$   .   .   .   .   .    .   .   .   .   .    . $``$  . $``$  .

We reduce the upper two rows as in the $`2\times 4`$ board, then Black moves next:

. $``$  .   .  $``$$``$$``$$``$ $``$$``$$``$$``$ $``$   . $``$  .   .    . $``$$``$$``$ $``$$``$$``$$``$ $``$   .   .   .   .    . $``$$``$$``$ $``$$``$$``$$``$ $``$   .   .   .   .    . $``$  . $``$ $``$$``$$``$$``$ $``$   .   .   .   .    . $``$  . $``$   . $``$$``$$``$ $``$   .   .   .   .    .   .   . $``$   . $``$$``$$``$ $``$   .   .   .   .    .   .   .   .    . $``$$``$$``$ $``$   .   .   .   .    .   .   .   .    .   . $``$$``$ $``$   .   .   .   .    .   .   .   .    .   . $``$  .

We reduce the upper two rows as in the $`2\times 6`$ board, then White moves next:

.   . $``$  . $``$  .  $``$$``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   . $``$  .  $``$  . $``$$``$$``$$``$ $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .  $``$  . $``$$``$$``$$``$ $``$$``$$``$$``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .  $``$  . $``$$``$$``$  .  $``$$``$  . $``$$``$  .  $`\stackrel{2}{}`$   .   .   .   .   .   .  $``$  .   . $``$$``$  .  $``$$``$  . $``$  .   .  $`\stackrel{4}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    . $``$  . $``$  .   .

We reduce the upper four rows as in the $`4\times 6`$ board, then White moves next:

. $``$  . $``$  .   .  $``$$``$$``$$``$$``$$``$ $``$$``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   . $``$  .   .  $``$$``$$``$$``$$``$$``$   . $``$$``$$``$$``$$``$ $`\stackrel{2}{}`$   .   .   . $``$  .   .    . $``$$``$$``$$``$$``$   . $``$$``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .    . $``$$``$$``$$``$$``$   .   . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .    .   . $``$  . $``$$``$   .   . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .    .   . $``$  .   .   .    .   . $``$  . $``$$``$ $`\stackrel{2}{}`$   .   .   .   .   .   .    .   .   .   .   .   .    .   . $``$  . $``$  .


format: text

text:
# The solution of a chiral random matrix model with complex eigenvalues

## 1 Introduction

The application of Random Matrix Models (RMM) in a variety of physical systems has a long history . Roughly speaking its applications can be divided into two classes. RMM can be either used to describe local properties. The correlations for example of energy levels often shown a universal behavior on the distance of the mean level spacing, making a RMM description possible. Choosing the RMM with the same global symmetries as the underlying Hamiltonian of the system fixes completely the form of the local spectral fluctuations. On the other hand RMM can be used as a combinatorial tool to count classes of graphs on random surfaces, which may then be interpreted as Feynman graphs of a corresponding Quantum Field Theory. Our investigations here belong to the first class of applications on a local level, and the corresponding correlation functions are often called microscopic.

In most cases RMM have to be seen as effective models owing their validity from symmetry considerations alone. However, in some cases the mapping to the theory one wishes to describe can be made exact, as for example in dynamical triangulations of random surfaces and its relation to Quantum Gravity  or in the application of RMM to the Dirac operator spectrum in four dimensional QCD . At the present stage the RMM we propose here as a model for QCD with chemical potential is just an effective or phenomenological model. But a more precise mapping to QCD via chiral perturbation theory may also be possible.

In many applications models of random matrices having real eigenvalues are considered. All such possible models have been classified  and all the corresponding correlation functions are known (for a complete list of results and references see e.g. ). On the other hand there are also physical situations where complex eigenvalues occur. As examples we mention localization in superconductors , dissipation and scattering in Quantum Chaos  or Quantum Chromodynamics (QCD) with a non-vanishing chemical potential . Other possible applications include the fractional Quantum Hall Effect as in  or a two-dimensional plasma of charged particles . A classification of all models with non-Hermitian matrices has been achieved more recently  and the number of possible cases exceeds by far those with real eigenvalues. But even when considering the simplest extension of the three RMM classes introduced by Dyson  much less is known. They consist of real symmetric ($`\beta =1`$), complex Hermitian ($`\beta =2`$) and quaternion self-dual matrices ($`\beta =4`$) where the Dyson index $`\beta `$ labels the ensemble by the power of the Jacobian diagonalizing the matrices, which is given by the Vandermonde determinant $`\mathrm{\Delta }`$. Due to their invariance these ensembles are called Gaussian Orthogonal, Unitary or Symplectic Ensemble, the GOE, GUE and GSE respectively.

In a seminal work the extension of these RMM into the complex plane has been obtained by Ginibre . He calculated the joint probability distribution function (j.p.d.f.) for $`\beta =2`$ and $`4`$ and partially for $`\beta =1`$ as well as all microscopic correlation functions for $`\beta =2`$. Since then progress has been slow. The full j.p.d.f. for $`\beta =1`$ was calculated much more recently in  but the correlation functions are still lacking up to date. The correlation functions for $`\beta =4`$ were found in . All these models are Gaussian ensembles with independently distributed matrix elements. More recently generalized Gaussian ensembles were considered containing a parameter $`\tau `$ that permits to interpolate between real and fully complex eigenvalues. The global density interpolating between the Wigner semi-circle on the real line and the constant density on a circular disc of Ginibre was found in  (see also  for numerical results of all three ensembles). Together with the introduction of the interpolating parameter $`\tau `$ the regime of so-called weak non-Hermiticity was discovered  for $`\beta =2`$ and $`1`$. For $`\beta =2`$ it interpolates smoothly between the know microscopic correlations of the GUE and those of Ginibre called strong non-Hermitian limit . The techniques to derive such results are either supersymmetry  or orthogonal polynomials  which also exist on the complex plane . For $`\beta =4`$ the $`\tau `$-dependent correlations were discovered very recently in  in both the weak and strong limit. New correlation functions for $`\beta =2`$ were also found in  where so-called Dirac mass terms were introduced in the application to three-dimensional QCD with complex eigenvalues.

From the RMM  which was first proposed to describe the QCD Dirac spectrum of real eigenvalues, the chiral Gaussian Unitary Ensemble (chGUE), we know that the model we are aiming for should belong to the class of chiral models. In the presence of a quark chemical potential it is also known that the Dirac eigenvalues become complex . We thus wish to define and solve such a chiral RMM with complex eigenvalues. The model is found by taking the know analogy between the GUE and the chGUE on the level of real eigenvalues and translating it into the complex plane. The starting point is the known complex GUE introduced in . In analogy to the real case and from the finding of Hermite polynomials in the complex plane for the non-chiral complex GUE in  we expect and do find Laguerre polynomials in the complex plane. This enables us to provide explicit solutions at a finite number $`N`$ of eigenvalues as well as in the weak and strong non-Hermitian large-$`N`$ limit.

The situation we wish to describe, QCD in the presence of a chemical potential, is quite delicate. The difficulties encountered when trying to do first principle calculations by using Monte Carlo simulations on a lattice are reviewed in . The are due to the problem of convergence for a determinant of a Dirac operator with complex eigenvalues. Despite the fact that recent progress was made in  the full phase diagram with $`\mu 0`$ remains unexplored so far. The analytical knowledge of microscopic correlation functions from complex chiral RMM could thus be very useful, in view of its success in predicting real eigenvalue correlations.

The chemical potential problem has already been addressed in quite a few works using RMM. In  the failure of the quenched approximation was illuminated by Stephanov. He also calculated the global eigenvalue density and its envelope as a functions of $`\mu `$. We will use his results to determine our non-Hermiticity parameter $`\tau `$ as a function of $`\mu `$ for small values of $`\mu `$. In  the temperature-density phase diagram of QCD with two light flavors was predicted using a RMM. A more refined model incorporating also vector and axial symmetries of the action was studied in . Effective models for a phase transition with the spectral density vanishing to an arbitrary power were introduced in . Furthermore, the analyticity properties of the partition function , problems of convergence  as well as the global symmetry of such Dirac operators  were analyzed using RMM. Finally first data for quenched simulations of QCD with $`\mu 0`$ have been confronted with RMM predictions, finding a crossover from the Wigner-Dyson class over strongly non-Hermitian, Ginibre type correlations to a Poisson distribution . There the nearest neighbor spacing of eigenvalues in the bulk from non-chiral RMM were compared to the data. Here, we wish to provide analytic information on all microscopic correlation functions at the origin, which are important for chiral symmetry breaking , using a chiral eigenvalue model.

The paper is organized as follows. In section 2 we introduce a chiral complex eigenvalue model. A justification is given why to call it chiral and why in particular it represents a complex extension of the chGUE. The identification of our parameter $`\tau `$ as a function of the chemical potential $`\mu `$ in QCD is made by comparing with the RMM . In the next section 3 we introduce the orthogonal polynomials belonging to our model, show that they are given by the Laguerre polynomials in the complex plane and give the exact solution for all correlators for a finite number of eigenvalues $`N`$. Sections 4 and 5 treat the large-$`N`$ limit at weak and strong non-Hermiticity, respectively. New correlation functions are found in both cases by taking appropriate limits of the Laguerre polynomials. We illustrate our findings with a few examples in each case. We also prove that the weak correlations interpolate between the known correlations of the chGUE and those in the strong limit from section 5. This is done by letting the weak non-Hermiticity parameter $`\alpha `$ approach zero or infinity in sections 4 and 5 respectively, explicitly checking that the correlations coincide. Our conclusions are presented in the last section 6. A brief summary of our results has been already published in .

## 2 The model

We first define our model in terms of complex eigenvalues $`z_{j=1,\mathrm{},N}`$ and then explain in detail why it is the generalization of the chGUE into the complex plane. The partition function is defined as

$$𝒵_{chiral}^{(a)}(\tau )\underset{j=1}{\overset{N}{}}\left(dz_jdz_j^{}w^{(a)}(z_j)\right)\left|\mathrm{\Delta }_N(z_1^2,\mathrm{},z_N^2)\right|^2,$$
(2.1)
where we have introduced the following weight function

$$w^{(a)}(z)=|z|^{2a+1}\mathrm{exp}\left[\frac{N}{1\tau ^2}\left(|z|^2\frac{\tau }{2}(z^2+z_{}^{}{}_{}{}^{2})\right)\right],$$
(2.2)
and $`\mathrm{\Delta }_N(z_1,\mathrm{},z_N)=_{k>l}^N(z_kz_l)`$ is the Vandermonde determinant. The parameter $`a>1`$ can be taken real for the time being. In the application to QCD it will be an integer, $`a=N_f+\nu `$, where $`N_f`$ labels the number of massless quark flavors and $`\nu `$ is the sector of topological charge. The parameter $`\tau [0,1]`$ controls the degree of non-Hermiticity. For $`\tau =1`$ we are back to the chGUE with real eigenvalues, as the weight functions (2.2) then reduces to a $`\delta `$-function in the imaginary part $`\mathrm{}\text{m}(z)`$ times a Gaussian weight for the real part $`\mathrm{}\text{e}(z)`$. On the other hand for $`\tau =0`$ the degree of non-Hermiticity is maximal, and we will see the individual rôle of $`\tau `$ in the weight of the real and imaginary part below.

The motivation for the definition of the model (2.1) comes from a comparison to the non-chiral model of complex eigenvalues, the complex extension of the GUE, introduced in . Let us therefore recall the relation between the GUE and chGUE for real eigenvalues first. The chGUE is defined in terms of a complex matrix $`W`$ of size $`N\times (N+\nu )`$

$`𝒵_{chGUE}^{(N_f,\nu )}`$ $`=`$ $`{\displaystyle 𝑑W𝑑W^{}det(WW^{})^{N_f}\text{e}^{Ng\text{tr}(WW^{})}}={\displaystyle _0^{\mathrm{}}}{\displaystyle \underset{j=1}{\overset{N}{}}}\left(d\lambda _j\lambda _j^{N_f+\nu }\text{e}^{Ng\lambda _j}\right)|\mathrm{\Delta }_N(\lambda _1,\mathrm{},\lambda _N)|^2`$ (2.3)
$`=`$ $`{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \underset{j=1}{\overset{N}{}}}\left(dx_j|x_j|^{2(N_f+\nu )+1}\text{e}^{Ngx_j^2}\right)|\mathrm{\Delta }_N(x_1^2,\mathrm{},x_N^2)|^2.`$
In the first step we have diagonalized and given the partition function in terms of the positive eigenvalues111To be precise these are called singular values. $`\lambda _j`$ of the matrix $`W`$ while in the second step we have simply substituted $`\lambda _j=x_j^2`$. Note the squares inside the Vandermonde due to this transformation. Now we compare to the GUE given in terms of a Hermitian matrix $`H`$ of size $`N\times N`$,

$$𝒵_{GUE}^{(2N_f)}=𝑑Hdet(H)^{2N_f}\text{e}^{Ng\text{tr}(H^2)}=_{\mathrm{}}^{\mathrm{}}\underset{j=1}{\overset{N}{}}\left(dx_jx_j^{2N_f}\text{e}^{Ngx_j^2}\right)|\mathrm{\Delta }_N(x_1,\mathrm{},x_N)|^2.$$
(2.4)
Both models can be solved using the method of orthogonal polynomials  and the corresponding sets are given by the generalized Laguerre polynomials for the chGUE and by the Hermite polynomials for the GUE (at $`N_f=0`$, for $`N_f>0`$ see ). Moreover, when taking the parameter $`a=N_f+\nu `$ to be real we can reconstruct the orthogonal polynomials of the chGUE on the full real line from the even subset of the orthogonal polynomials of the GUE. Because of the squares in the Vandermonde in eq. (2.3) we only need even polynomials there. This relation also holds for more general, non-Gaussian weight functions (see e.g. in ). For $`a=1/2`$ this is nothing else than the known relation between Hermite and Laguerre polynomials  (see eq. (3.8) below).

Let us now turn to the complex generalization of the GUE as introduced in . The Hermitian matrix $`H`$ is replaced by a complex matrix

$$J=H+i\sqrt{\frac{1\tau }{1+\tau }}A.$$
(2.5)
with $`\tau [0,1]`$. The weight for both the Hermitian and anti-Hermitian part of $`J`$, the Hermitian matrices $`H`$ and $`A`$ respectively, is chosen to be Gaussian with variance $`(1+\tau )/2N`$. We therefore obtain

$`𝒵^{(2N_f)}(\tau )`$ $``$ $`{\displaystyle 𝑑J𝑑J^{}det(JJ^{})^{N_f}\mathrm{exp}\left[\frac{N}{1\tau ^2}\text{tr}\left(JJ^{}\frac{\tau }{2}(J^2+(J^{})^2)\right)\right]}`$
$`=`$ $`{\displaystyle \underset{j=1}{\overset{N}{}}\left(dz_jdz_j^{}|z_j|^{2N_f}\mathrm{exp}\left[\frac{N}{1\tau ^2}\left(|z_j|^2\frac{\tau }{2}(z_j^2+z_j^2)\right)\right]\right)|\mathrm{\Delta }_N(z_1,\mathrm{},z_N)|^2}.`$
For averages over the matrix elements of $`J`$ this corresponds to

$$J_{kl}J_{lk}=\frac{\tau }{N},J_{kl}J_{kl}^{}=\frac{1}{N},$$
(2.7)
which illustrates the interpolating rôle of $`\tau `$: for $`\tau =1`$ we have $`J_{lk}=J_{kl}^{}`$ and thus Hermitian matrices whereas for $`\tau =0`$ all $`J_{kl}`$ are mutually independent corresponding to maximal non-Hermiticity. In the latter case the model was already defined and solved by Ginibre in  where the orthogonal polynomials are monomials in the complex eigenvalues $`z_j`$ of $`J`$. Here, we can study the transition between the GUE and the Ginibre ensemble and the corresponding polynomials were found to be Hermite polynomials in the complex plane . Using the same reasoning as in the mapping between the real eigenvalues model of the GUE eq. (2.4) and the chGUE eq. (2.3), eq. (2) immediately leads to our model eq. (2.1) above. This way we have solved the problem of how to extend the positive real eigenvalues (2.3) into the complex plane. We may of course ask ourselves to what kind of matrix representation eq. (2.1) would correspond to. We would have to express eq. (2.1) in terms of a different matrix $`\stackrel{~}{J}`$, probably with two different complex matrices now, in the form $`\stackrel{~}{J}WW^{}+iVV^{}`$. However, we have not been able to find such a representation so far.

Let us compare to a different matrix model which has been introduced by Stephanov for QCD with non-vanishing chemical potential ,

$$𝒵^{(N_f,\nu )}(\mu )𝑑W𝑑W^{}det\left(\begin{array}{cc}0& iW+\mu \\ iW^{}+\mu & 0\end{array}\right)^{N_f}\text{e}^{Ng\text{tr}(WW^{})}.$$
(2.8)
Here, the matrix inside the determinant replaces the QCD Dirac operator with the chemical potential added as $`\gamma _0\mu `$. The disadvantage from adding a constant matrix to the chiral random matrix is that the model can no longer be written in terms of eigenvalues of the matrix $`W`$. Our idea is to use the model eq. (2.1) instead and to suppose that on the scale of the mean level spacing of the complex Dirac operator eigenvalues the microscopic correlations are the same. A somewhat similar observation has been made in  where a chiral matrix model with temperature was considered. In order to capture the effect of the lowest Matsubara frequency a constant matrix $`i\gamma _0t`$ was added to the Dirac matrix. An analysis in terms of eigenvalues of the matrix $`WW^{}`$ is also no longer possible, although the original Dirac eigenvalues remain real in this case. However, the microscopic correlations remain the same compared to the model at $`t=0`$, when translating to the same mean level spacing . To avoid misunderstandings let us stress that we do not claim that the correlations at $`\mu =0`$ and $`\mu 0`$ are the same but that (2.8) at $`\mu 0`$ and our model at $`\tau <1`$ share the same microscopic correlation functions.

In order to relate these two parameters we compare the macroscopic spectral densities of the two models. In our model it can be read off from  since the preexponential factors in the weight eq. (2.2) are subdominant in the macroscopic large-$`N`$ limit,

$$\rho _\tau (z)=\frac{1}{\pi (1\tau ^2)},\text{if}\frac{x^2}{(1+\tau )^2}+\frac{y^2}{(1\tau )^2}1,$$
(2.9)
where $`z=x+iy`$. The density is constant and bounded by an ellipse, where for $`\tau =0`$ we recover the result of . On the other hand for eq. (2.8) the macroscopic density has been calculated in ,

$$\rho _\mu (z)=\frac{1}{4\pi }\left(\frac{\mu ^2+y^2}{(\mu ^2y^2)^2}1\right),$$
(2.10)
where the eigenvalues are bounded by the following curve222In our conventions the Dirac eigenvalues are real for $`\mu =0`$, as it should have become clear by now. In comparison to ref.  this means that we interchange real and imaginary part, $`xy`$, compared to there.

$$0=y^4(x^2+4\mu ^2)+y^2(1+2\mu ^2(2x^24\mu ^2))+\mu ^4(x^24(1\mu ^2)).$$
(2.11)
The aim of the two models (2.1) and (2.8) is to describe the fluctuations of Dirac eigenvalues close to the origin, because of their relevance for chiral symmetry breaking from the Banks-Casher relation . We will therefore restrict ourselves to small values of $`\mu `$ since otherwise the determinant in eq. (2.8) is completely dominated by $`\mu `$. Another reason for small $`\mu `$ is that we wish to stay in the phase with broken chiral symmetry. For $`\mu 1`$ the curve (2.11) splits into two and the vanishing of the macroscopic spectral density $`\rho _\mu (0)`$ indicates through the Banks-Casher relation that the chiral phase transition has taken place. If we solve the biquadratic equation (2.11) for the imaginary part $`y`$ and expand in $`\mu `$ we obtain

$$y^2=\mu ^4(4x^2)+𝒪(\mu ^6).$$
(2.12)
Expanding the density eq. (2.10) in $`\mu 1`$ we can therefore neglect $`y^2`$ and finally arrive at

$$\rho _\mu (z)=\frac{1}{4\pi \mu ^2},\text{if}\frac{x^2}{4}+\frac{y^2}{4\mu ^2}1.$$
(2.13)
Comparing eqs. (2.9) and (2.13) we identify

$$4\mu ^2(1\tau ^2),$$
(2.14)
which is valid for small chemical potential $`\mu `$ and the parameter $`\tau `$ close to unity meaning small non-Hermiticity. We have now identified all the parameters in our model with the corresponding quantities in QCD. In contrast to the model (2.8) by Stephanov we will not be able to study the chiral phase transition since our $`\rho _\tau (z)`$ will remain constant for all $`\tau [0,1)`$. On the other hand we will be able to calculate all correlation functions, for finite-$`N`$ as well in two different microscopic scaling limits in the next sections. This has not been achieved so far for the model (2.8), where only the macroscopic density is known .

We finally comment on the presence of the absolute value in the weight eq. (2.2) which is chosen to make the partition function real. In the model (2.8) no absolute value of the Dirac determinant is present. Let us however emphasize that also in the real eigenvalue model eq. (2.3) an absolute value is present due to the mapping from the positive to the full real line, even for zero quark flavors $`N_f=0`$.

## 3 The Solution from Orthogonal Polynomials

We now turn to the solution of our model for a finite number of eigenvalues $`N`$, where we use the powerful method of orthogonal polynomials . In the two following sections we then take the large-$`N`$ limit. The orthogonal polynomials in the complex plane we are searching for are defined with respect to the weight function eq. (2.2),

$$𝑑z𝑑z^{}w^{(a)}(z)P_k^{(a)}(z)P_l^{(a)}(z^{})=\delta _{kl}.$$
(3.1)
All $`k`$-point correlation functions defined as

$$\rho _N^{(a)}(z_1,\mathrm{},z_k)\underset{j=k+1}{\overset{N}{}}dz_jdz_j^{}\underset{l=1}{\overset{N}{}}w^{(a)}(z_l)\left|\mathrm{\Delta }_N(z_1^2,\mathrm{},z_N^2)\right|^2,$$
(3.2)
can be expressed in terms of the kernel of orthogonal polynomials

$$K_N^{(a)}(z_1,z_2^{})[w^{(a)}(z_1)w^{(a)}(z_2^{})]^{\frac{1}{2}}\underset{k=0}{\overset{N1}{}}P_k^{(a)}(z_1)P_k^{(a)}(z_2^{}).$$
(3.3)
Due to the invariance of the determinant the monomial powers inside the Vandermonde $`\mathrm{\Delta }_N`$ in eq. (2.1) can be replaced by the orthogonal polynomials and we arrive at

$$\rho _N^{(a)}(z_1,\mathrm{},z_k)=\underset{1i,jk}{det}\left[K_N^{(a)}(z_i,z_j^{})\right].$$
(3.4)
In eq. (2.1) only even powers of $`z_j`$ occur inside the Vandermonde $`\mathrm{\Delta }_N`$ and we thus only need even polynomials. From the known relation between Hermite and Laguerre polynomials  for $`a=1/2`$ we expect to obtain Laguerre polynomials of the squared argument, $`P_k^{(a)}(z)L_k^a(z^2)`$, and we will find that this is indeed the case (see eq. (3.15) below).

In order to derive the orthogonality of the Laguerre polynomials in the complex plane we define the normalization integral

$`f^{(a)}(\tau )`$ $``$ $`{\displaystyle 𝑑z𝑑z^{}w^{(a)}(z)}`$
$`=`$ $`N^{a\frac{3}{2}}\pi \mathrm{\Gamma }\left(a+{\displaystyle \frac{3}{2}}\right)(1\tau ^2)^{\frac{a}{2}+\frac{3}{4}}P_{a+\frac{3}{2}}\left({\displaystyle \frac{1}{\sqrt{1\tau ^2}}}\right)`$
where $`P_{a+\frac{3}{2}}(x)`$ is the Legendre function. While the expression given is exact for finite and infinite $`N`$ it will simplify in the weak non-Hermiticity limit in section 4 where $`1\tau ^2`$ is rescaled with $`N`$. Following the idea of ref.  we use the invariance of the integral eq. (3) under reparametrization to make the generating function of the Laguerre polynomials appear. Performing a change of variables $`z\text{e}^{i\phi }z`$ inside the integral eq. (3) we obtain from eq. (2.2)

$`f^{(a)}(\tau )`$ $`=`$ $`{\displaystyle 𝑑z𝑑z^{}|z|^{2a+1}\mathrm{exp}\left[\frac{N}{1\tau ^2}\left(|z|^2\frac{\tau }{2}(\text{e}^{i2\phi }z^2+\text{e}^{i2\phi }z^2)\right)\right]}`$
$`1`$ $`=`$ $`\mathrm{exp}\left[{\displaystyle \frac{(\text{e}^{i2\phi }1)\tau ^2}{1\tau ^2}}\left({\displaystyle \frac{Nz^2}{2\tau }}\right)\right]\mathrm{exp}\left[{\displaystyle \frac{(\text{e}^{i2\phi }1)\tau ^2}{1\tau ^2}}\left({\displaystyle \frac{Nz_{}^{}{}_{}{}^{2}}{2\tau }}\right)\right],`$ (3.6)
where the average is taken with respect to the weight function eq. (2.2) and we have divided by $`f^{(a)}(\tau )`$ in order to normalize. We now wish to obtain the following generating functional for the Laguerre polynomials, which is also valid for complex arguments $`Z`$:

$$(1u)^{a1}\mathrm{exp}\left[\frac{u}{u1}Z^2\right]=\underset{k=0}{\overset{\mathrm{}}{}}L_k^a(Z^2)u^k,|u|<1,$$
(3.7)
and similarly for complex conjugate arguments. The split into variables $`u`$ and $`Z^2`$ is not unique in eq. (3.6). We will use the known results  for the Hermite polynomials $`He_n`$ of the model eq. (2) to read off the argument in the case $`a=1/2`$ using

$$He_{\mathrm{\hspace{0.17em}2}k}\left(\sqrt{\frac{N}{\tau }}z\right)=(1)^k2^kk!L_k^{\frac{1}{2}}\left(\frac{Nz^2}{2\tau }\right).$$
(3.8)
We therefore choose $`Z^2=\frac{Nz^2}{2\tau }`$ and

$$\frac{u}{u1}\frac{(\text{e}^{i2\phi }1)\tau ^2}{1\tau ^2},$$
(3.9)
which can be written as

$$u=\frac{\tau ^2(1\text{e}^{i2\phi })}{1\tau ^2\text{e}^{i2\phi }}.$$
(3.10)
It is complex and satisfies $`|u|<1`$. We now multiply eq. (3.6) with $`[(1u)(1u^{})]^{a1}`$ to obtain

$$[(1u)(1u^{})]^{a1}=\underset{k,l=0}{\overset{\mathrm{}}{}}L_k^a\left(\frac{Nz^2}{2\tau }\right)L_k^a\left(\frac{Nz^2}{2\tau }\right)u^ku^l,$$
(3.11)
where we have inserted the generating functional eq. (3.7). Using the fact that

$$uu^{}=\frac{4\tau ^4\mathrm{sin}^2\phi }{(1\tau ^2)^2+4\tau ^2\mathrm{sin}^2\phi }$$
(3.12)
together with the definition (3.9) it is easy to see that the left hand side of eq. (3.11) only depends on the combination $`uu^{}`$ and we obtain

$$[(1u)(1u^{})]^{a1}=[1\tau ^2uu^{}]^{a1}=\underset{k=0}{\overset{\mathrm{}}{}}\frac{\mathrm{\Gamma }(a+1+k)}{\mathrm{\Gamma }(a+1)k!}\frac{(uu^{})^k}{\tau ^{2k}},$$
(3.13)
which converges due to $`\tau ^2uu^{}<1`$ from eq. (3.12). Consequently also the right hand side of eq. (3.11) depends only on the combination $`uu^{}`$ and thus the Laguerre polynomials have to be orthogonal. By comparing coefficients of eqs. (3.13) and (3.11) we arrive at

$$L_k^a\left(\frac{Nz^2}{2\tau }\right)L_k^a\left(\frac{Nz^2}{2\tau }\right)=\delta _{kl}\frac{\mathrm{\Gamma }(a+1+k)}{\mathrm{\Gamma }(a+1)k!}\frac{1}{\tau ^{2k}}.$$
(3.14)
The orthogonal polynomials from eq. (3.1) are thus finally given as

$$P_k^{(a)}(z)\left(\frac{\mathrm{\Gamma }(a+1+k)}{\mathrm{\Gamma }(a+1)k!}f^{(a)}(\tau )\right)^{\frac{1}{2}}(\tau )^kL_k^a\left(\frac{Nz^2}{2\tau }\right).$$
(3.15)
The phase factor $`(1)^k`$ which is chosen arbitrarily is taken such that the relation (3.8) is reproduced at $`a=1/2`$. All $`k`$-point correlation functions are therefore completely determined inserting the polynomials $`P_k^{(a)}(z)`$ into eqs. (3.3) and (3.4). We only give the expression for the kernel at finite-$`N`$,

$$K_N^{(a)}(z_1,z_2^{})=[w^{(a)}(z_1)w^{(a)}(z_2^{})]^{\frac{1}{2}}\frac{\mathrm{\Gamma }(a+1)}{f^{(a)}(\tau )}\underset{k=0}{\overset{N1}{}}\frac{k!}{\mathrm{\Gamma }(a+1+k)}\tau ^{2k}L_k^a\left(\frac{Nz_1^2}{2\tau }\right)L_k^a\left(\frac{Nz_2^2}{2\tau }\right).$$
(3.16)
Let us point out that although we have checked our results by comparing to the orthogonal Hermite polynomial of the model (2) at $`a=1/2`$ we cannot do the same check with the correlation functions. The reason is that in the model (2) also the odd polynomials contribute to the correlation functions.

In the following sections we will investigate the large-$`N`$ limit. For that purpose usually a different form of the kernel eq. (3.3) is given. It only contains the polynomials of order $`N`$ and $`N1`$ and is derived from the Christoffel-Darboux identity. However, due to the $`\tau `$ dependence of the arguments in eq. (3.15) this identity no longer holds in the complex plane333I wish to thank E. Kanzieper for pointing out this fact to me.. The modified Christoffel-Darboux identity now contains polynomials of all orders, $`0,\mathrm{},N`$. A similar fact occurs in the two-matrix model (see e.g. ). The large-$`N`$ limit is no longer governed by the asymptotic polynomials alone and we will have to use special properties of the Laguerre polynomials to achieve our goal in the next sections.

Before we continue let us explain why we did not include Dirac quark masses into our model, in contrast to . In the non-chiral model mass terms of the form $`_f^{N_f}|zim_f|^2`$ were included in the weight function. The corresponding correlation functions were calculated by relating them to massless correlations, using the fact that the masses can be produced from a larger Vandermonde . Using the same technique in our model eq. (2.1) we would only be able to treat additional terms of the form $`_f^{N_f}(z^2+m_f^2)(z^2+m_f^2)`$ in the weight (2.2). While these terms might be interesting for other applications they are not of the right form for QCD mass terms of a complex Dirac matrix. For this reason we refrain from deriving such correlation functions here.

## 4 The weak non-Hermiticity limit

The large-$`N`$ limit at weak non-Hermiticity was introduced in  and is defined as follows. We take the limit $`\tau 1`$ that leads to Hermitian matrices at the same time as $`N\mathrm{}`$ such that the combination

$$\underset{N\mathrm{}}{lim}N(1\tau ^2)\alpha ^2$$
(4.1)
is kept finite. In this limit the macroscopic density eq. (2.9) depends on real eigenvalues only. It becomes the Wigner semi-circle, $`\rho (x)=\frac{1}{2\pi }\sqrt{4x^2}`$, for the Gaussian weight we have chosen, with support $`[2,2]`$ on the real line only. However, the properly rescaled microscopic correlations remain complex and are different from those of real eigenvalues as well as from the strong non-Hermiticity limit where $`\tau <1`$. Because of the identification we have made between $`\tau `$ and $`\mu `$, eq. (2.14), eq. (4.1) invokes to send also $`\mu 0`$ as $`N\mathrm{}`$ while keeping

$$4N\mu ^2=\alpha ^2$$
(4.2)
fixed444In ref.  an attempt was made to relate $`\mu `$ to $`\alpha `$ by comparing the macroscopic density (2.10) to the average of microscopic eigenvalues and a wrong power was obtained.. In other words the weak non-Hermiticity parameter $`\alpha ^2`$ directly measures the chemical potential in the microscopic scaling limit. The rescaling of $`\mu `$ is similar to that of the quark masses $`m_f`$, however with a different power in $`N`$. It makes sure that the eigenvalues in the Dirac determinant are not completely dominated by the masses or the chemical potential (see in eq. (2.8)). Namely in the weak non-Hermitian limit at the origin we also rescale the complex eigenvalues keeping

$$N(\mathrm{}\text{e}z+i\mathrm{}\text{m}z)=Nz\xi ,$$
(4.3)
The matrix size $`N`$ corresponds to the volume on the lattice. It has been mentioned in  that in the RMM eq. (2.8) the numerical effort to obtain convergence grows exponentially with $`N\mu ^2`$. Keeping it fixed here according to eq. (4.2) should make a comparison to data feasible.

Eqs. (4.1) - (4.3) define our microscopic origin scaling limit in the complex plane at weak non-Hermiticity. The kernel eq. (3.3) and correlation functions eq. (3.4) also have to be rescaled with the mean level spacing $`1/N`$ of the eigenvalues. In the definition of the correlation functions for each variable $`z_j`$ we integrate over its real and imaginary part and we obtain one power $`1/N`$ from each integration. The microscopic kernel and correlation functions are therefore defined as follows in the weak non-Hermiticity limit:

$`K_S^{(a)}(\xi _1,\xi _2^{})`$ $``$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N^2}}K_N^{(a)}({\displaystyle \frac{\xi _1}{N}},{\displaystyle \frac{\xi _2^{}}{N}})`$
$`\rho _S^{(a)}(\xi _1,\mathrm{},\xi _k)`$ $``$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N^{2k}}}\rho _N^{(a)}({\displaystyle \frac{\xi _1}{N}},\mathrm{},{\displaystyle \frac{\xi _k}{N}}).`$ (4.4)
When looking at the kernel at finite-$`N`$ eq. (3.16) and the appropriate rescaling of the eigenvalues, eq. (4.3), we observe that we are missing a power in $`N`$ inside the argument of the Laguerre polynomials. The asymptotic of the Laguerre polynomials,

$$\underset{k\mathrm{}}{lim}k^aL_k^a(Z^2)=(kZ^2)^{\frac{a}{2}}J_a(2\sqrt{kZ^2})$$
(4.5)
suggests to introduce a variable $`t\frac{k}{N}`$ and thus to replace the sum in eq. (3.16) by an integral, $`_{k=0}^{N1}N_0^1𝑑t`$. In doing so we write everything in terms of the variables $`t`$ and $`\xi _j`$. Under the integral we can thus replace everywhere the Laguerre polynomials by $`J`$-Bessel functions using eg. (4.5) since a finite $`t=\frac{k}{N}(0,1]`$ means that $`k`$ has to become large and the point $`t=0`$ is of measure zero.

In the following we separately give the asymptotic of each factor in eq. (3.16) before stating the final answer. The weight functions contain already the right powers of $`N`$ in the exponential and using eq. (4.1) we obtain

$$\underset{N\mathrm{}}{lim}w^{(a)}(z)^{\frac{1}{2}}=N^{a\frac{1}{2}}|\xi |^{a+\frac{1}{2}}\mathrm{exp}\left[\frac{1}{\alpha ^2}(\mathrm{}\text{m}\xi )^2\right].$$
(4.6)
To calculate the weak limit of the normalization integral $`f^{(a)}(\tau )`$ in eq. (3) we need to know the asymptotic of the Legendre functions, given by

$$\underset{\tau 1}{lim}P_{a+\frac{1}{2}}\left(\frac{1}{\sqrt{1\tau ^2}}\right)=\frac{2^{a+\frac{1}{2}}\mathrm{\Gamma }(a+1)}{\sqrt{\pi }\mathrm{\Gamma }(a+\frac{3}{2})}(1\tau ^2)^{\frac{a}{2}\frac{1}{4}}.$$
(4.7)
This leads to

$$\underset{\tau 1}{lim}f^{(a)}(\tau )=\sqrt{2\pi \alpha ^2}N^{a2}2^a\mathrm{\Gamma }(a+1).$$
(4.8)
Under the integral we first replace

$$\underset{k\mathrm{}}{lim}\frac{k!}{\mathrm{\Gamma }(a+1+k)}=N^at^a.$$
(4.9)
Rewriting eq. (4.1) as $`\tau ^2=1\alpha ^2/N`$ the power in $`\tau `$ turns into an exponential,

$$\underset{N\mathrm{}}{lim}\left(\tau ^{2k}=\text{e}^{k\mathrm{ln}(\tau ^2)}\right)=\text{e}^{t\alpha ^2}.$$
(4.10)
Finally The Laguerre polynomials are replaced as

$$\underset{k,N\mathrm{}}{lim}L_k^a\left(\frac{Nz^2}{2\tau }\right)=N^a(2t)^{\frac{a}{2}}\xi ^aJ_a(\sqrt{2t}\xi ).$$
(4.11)
Putting together eqs. (4.6) - (4.11) all powers of $`N`$ cancel as they should and we obtain

$$K_S^{(a)}(\xi _1,\xi _2^{})=\frac{|\xi _1\xi _2^{}|^{\frac{1}{2}}}{\sqrt{2\pi \alpha ^2}}\frac{|\xi _1\xi _2^{}|^a}{(\xi _1\xi _2^{})^a}\text{e}^{\frac{1}{\alpha ^2}\left((\mathrm{}m\xi _1)^2+(\mathrm{}m\xi _2^{})^2\right)}_0^1𝑑t\text{e}^{\alpha ^2t}J_a(\sqrt{2t}\xi _1)J_a(\sqrt{2t}\xi _2^{}).$$
(4.12)
When inserting the kernel into the determinant eq. (3.4) for the correlators all factors apart from the integral can be taken out. In particular the second factor cancels due to the occurrence of the $`\xi _j^a`$ and $`\xi _j^a`$ in each column and row. We arrive at the microscopic, weakly non-Hermitian correlation functions:

$$\rho _S^{(a)}(\xi _1,\mathrm{},\xi _k)=\underset{l=1}{\overset{k}{}}\left(\frac{|\xi _l|}{\sqrt{2\pi \alpha ^2}}\text{e}^{\frac{2}{\alpha ^2}(\mathrm{}m\xi _l)^2}\right)\underset{1i,jk}{det}\left[_0^1𝑑t\text{e}^{\alpha ^2t}J_a(\sqrt{2t}\xi _i)J_a(\sqrt{2t}\xi _j^{})\right].$$
(4.13)
They are clearly different from the correlations of the non-chiral model eq. (2) as calculated for $`a=0`$ in  and for $`a=N_f`$ massless flavors in . There, the product of two $`J`$-Bessel functions is replaced by a single cosine, $`\mathrm{cos}(\sqrt{2t}(\xi _i\xi _j^{}))`$ which corresponds to a half-integer Bessel $`J_{\frac{1}{2}}`$.

As an important check we can compare to the correlation functions of real eigenvalues  of the chGUE eq. (2.3) which have been shown to be universal . We take the Hermitian limit by sending $`\alpha ^20`$ which corresponds to $`\tau =1`$. The exponential prefactors become $`\delta `$-functions for the imaginary parts of the eigenvalues, as they should. The integral inside the determinant then makes the universal Bessel kernel (of squared arguments) appear, reproducing the known correlation functions of :

$$_0^1𝑑tJ_a(\sqrt{2t}x_1)J_a(\sqrt{2t}x_2)=\frac{x_1J_{a+1}(\sqrt{2}x_1)J_a(\sqrt{2}x_2)x_2J_{a+1}(\sqrt{2}x_2)J_a(\sqrt{2}x_1)}{\sqrt{2}(x_1^2x_2^2)}.$$
(4.14)
To give an example for eq. (4.13) we show the microscopic density in the weak limit for two values of $`a`$ in Fig 1. For one quark flavor ($`a=1`$) the level repulsion at the origin is stronger as expected. The plot continues symmetrically from the given first quadrant into the full complex plane by reflecting along the real and imaginary axis. In cutting along the positive real axis we can see the oscillations familiar from the correlations of real eigenvalues. Each maximum corresponds to the location of a single eigenvalue in the complex plane. We also show the $`\alpha `$-dependence of the quenched microscopic density in Fig. 2. For increasing $`\alpha `$ and thus for increasing rescaled chemical potential $`\mu `$ the eigenvalues spread further into the complex plane. In particular the density also builds up along the imaginary axis. As we will see in the next section in the limit $`\alpha \mathrm{}`$ we obtain the microscopic correlations at strong non-Hermiticity to be defined below. The limiting picture to be compared with is Fig. 3 below with the quenched density on the left.

## 5 The strong non-Hermiticity limit

We now turn to the strong non-Hermiticity limit. In this limit $`\tau [0,1)`$ is kept fixed in the large-$`N`$ limit and consequently also $`\mu `$ from eq. (2.14) is kept finite and unscaled, in contrast to eq. (4.2). The eigenvalues are now rescaled differently, namely with the square root of $`N`$ ,

$$\sqrt{N}(\mathrm{}\text{e}z+i\mathrm{}\text{m}z)=\sqrt{N}z\xi .$$
(5.1)
This defines our microscopic origin limit at strong non-Hermiticity. In consequence we also have to change the rescaling of the microscopic kernel and correlation functions accordingly,

$`K_S^{(a)}(\xi _1,\xi _2^{})`$ $``$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}K_N^{(a)}({\displaystyle \frac{\xi _1}{\sqrt{N}}},{\displaystyle \frac{\xi _2^{}}{\sqrt{N}}}),`$
$`\rho _S^{(a)}(\xi _1,\mathrm{},\xi _k)`$ $``$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N^k}}\rho _N^{(a)}({\displaystyle \frac{\xi _1}{\sqrt{N}}},\mathrm{},{\displaystyle \frac{\xi _k}{\sqrt{N}}}).`$ (5.2)
In the strong scaling limit eq. (5.1) the argument of the Laguerre polynomials in eq. (3.16) can be rewritten in terms of the scaling variable $`\xi `$ alone. In particular we cannot use the asymptotic eq. (4.5) for the Laguerre polynomials any longer. Fortunately there is an identity for an infinite sum of Laguerre polynomials at hand ,

$$\underset{k=0}{\overset{\mathrm{}}{}}\frac{k!}{\mathrm{\Gamma }(a+1+k)}\tau ^{2k}L_k^a(Z_1^2)L_k^a(Z_2^2)=\frac{(Z_1^2Z_2^2\tau ^2)^{\frac{a}{2}}}{1\tau ^2}\mathrm{exp}\left[\frac{\tau ^2}{1\tau ^2}(Z_1^2+Z_2^2)\right]I_a\left(2\frac{\sqrt{Z_1^2Z_2^2\tau ^2}}{1\tau ^2}\right),$$
(5.3)
which is the analog of Mehlers formula for the Hermite polynomials used in  to derive the strong correlation functions. We can thus immediately read off the large-$`N`$ limit of the kernel eq. (3.16) and obtain

$`K_S^{(a)}(\xi _1,\xi _2^{})`$ $`=`$ $`{\displaystyle \frac{2^a\mathrm{\Gamma }(a+1)}{\pi \mathrm{\Gamma }\left(a+\frac{3}{2}\right)(1\tau ^2)^{\frac{a}{2}+\frac{7}{4}}P_{a+\frac{3}{2}}\left(\frac{1}{\sqrt{1\tau ^2}}\right)}}{\displaystyle \frac{|\xi _1\xi _2^{}|^{a+\frac{1}{2}}}{(\xi _1\xi _2^{})^a}}`$
$`\times \mathrm{exp}\left[{\displaystyle \frac{1}{2(1\tau ^2)}}\left(|\xi _1|^2+|\xi _2^{}|^2{\displaystyle \frac{\tau }{2}}(\xi _{1}^{}{}_{}{}^{2}\xi _1^2+\xi _2^2\xi _{2}^{}{}_{}{}^{2})\right)\right]I_a\left({\displaystyle \frac{\xi _1\xi _2^{}}{1\tau ^2}}\right).`$
Here we have inserted the explicit expression for the normalization integral eq. (3). After taking out factors from the determinant the correlation functions again simplify considerably and our final result reads

$$\rho _S^{(a)}(\xi _1,\mathrm{},\xi _k)=\underset{l=1}{\overset{k}{}}(\frac{2^a\mathrm{\Gamma }(a+1)|\xi _l|}{\pi \mathrm{\Gamma }\left(a+\frac{3}{2}\right)(1\tau ^2)^{\frac{a}{2}+\frac{7}{4}}P_{a+\frac{3}{2}}\left(\frac{1}{\sqrt{1\tau ^2}}\right)}\text{e}^{\frac{1}{1\tau ^2}|\xi _l|^2})\underset{1i,jk}{det}\left[I_a\left(\frac{\xi _i\xi _j^{}}{1\tau ^2}\right)\right].$$
(5.5)
In ref.  correlation functions for a charged two-dimensional plasma with fractional charges at the origin have been obtained, in what we call strong non-Hermiticity limit. However, since the interaction term induced by the Vandermonde determinant of squared arguments in our model eq. (2.1) is different from that of  the correlation functions obtained there also differ from ours.

A consistency check for the correlation functions eq. (5.5) can be obtained from the weakly non-Hermitian correlations eq. (4.13) by taking the limit $`\alpha \mathrm{}`$ there. We evaluate the integral inside the determinant as follows,

$`{\displaystyle _0^1}𝑑t\text{e}^{\alpha ^2t}J_a(\sqrt{2t}\xi _i)J_a(\sqrt{2t}\xi _j^{})`$ $`=`$ $`{\displaystyle \frac{1}{\alpha ^2}}{\displaystyle _0^{\mathrm{}}}𝑑s\text{e}^sJ_a\left({\displaystyle \frac{\sqrt{2s}}{\alpha }}\xi _i\right)J_a\left({\displaystyle \frac{\sqrt{2t}}{\alpha }}\xi _j^{}\right)`$ (5.6)
$`=`$ $`{\displaystyle \frac{1}{\alpha ^2}}\mathrm{exp}\left[{\displaystyle \frac{1}{2\alpha ^2}}(\xi _1^2+\xi _2^2)\right]I_a\left({\displaystyle \frac{\xi _1\xi _2^{}}{\alpha ^2}}\right)`$
When identifying $`\alpha ^2=1\tau ^2`$ and taking out the exponential of the determinant in eq. (4.13) we immediately recover the strong correlations eq. (5.5). In order to match the normalizations we also have to expand the Legendre function for large argument, according to eq. (4.7). We have thus control over the full parameter range starting from real eigenvalues via weak to strong non-Hermitian correlation functions.

As an example for eq. (5.5) we depict the strong microscopic density in Fig. 3 for zero and one massless flavors. The value for $`\tau =0.5`$ corresponds to $`\mu =\sqrt{3}/40.43`$ in our units, according to eq. (2.14). The microscopic spectral density develops a hole at the origin and becomes flat for large values. This has indeed been observed in quenched lattice data for intermediate values of the chemical potential . For one massless flavor ($`a=1`$) the level repulsion at the origin is again stronger and the barrier gets flattened out. The picture is very much reminiscent of the microscopic density with massless flavors of the non-chiral model  in the strong limit (compared to Fig. 3 there).

When getting closer to the Hermitian limit by raising $`\tau 1`$ or equivalently lowering $`\mu 0`$ the repulsion at the origin gets much more pronounced. In Fig. 4 we have depicted the same densities as in Fig. 3 but for $`\tau =\sqrt{21}/50.9`$ corresponding to $`\mu =0.2`$. Both values for $`\mu `$ in Figs. 3 and 4 are in the broken phase when comparing to ref. . There, the phase transition occurs at a critical value $`\mu _c=1`$ as it follows from eq. (2.11). Even if we take the extreme case of maximal non-Hermiticity which corresponds to $`\tau =0`$ in our model we will stay inside the phase with broken chiral symmetry. This can be seen when assuming that the relation $`(\text{2.14})`$ is still approximately valid, leading to $`\mu (\tau =0)=\frac{1}{2}`$.

## 6 Conclusions

We have introduced and solved a new class of chiral RMM with complex eigenvalues, that corresponds to the extension of the chGUE into the complex plane. It was shown that the orthogonal polynomials of our model are given by the Laguerre polynomials in the complex plane. Consequently all $`k`$-point correlation functions could be given exactly for a finite number of eigenvalues $`N`$ in terms of the kernel of these polynomials. We then investigated two different large-$`N`$ limits with weak and strong non-Hermiticity. In both cases explicit results were given for all correlation functions in terms of the two different limiting kernels. Furthermore, we could prove that the results for weak non-Hermiticity interpolate between the known correlation functions of real eigenvalues of the chGUE and those of strong non-Hermiticity, taking the limit of the weak non-Hermiticity parameter $`\alpha 0`$ or $`\mathrm{}`$, respectively.

As an application of our model we have proposed that it describes the correlations of QCD Dirac eigenvalues close to the origin in the presence of a small chemical potential $`\mu `$. For that purpose we related our parameter $`\tau `$ that measures the non-Hermiticity with the chemical potential as it occurs in QCD. In the identification we compared to another matrix model that incorporates the symmetries of the Dirac operator with $`\mu 0`$ more closely. It remains to compare our predictions to lattice data in four-dimensional QCD yet to be generated and to see if the success of RMM in predicting real eigenvalues extends to the complex plane. It would be also very interesting to find other applications too, in particular given the interpretation of the complex eigenvalues as positions of charges distributed in a two-dimensional plane.

So far we have only defined our model as an eigenvalue model and obtained its chiral interpretation by analogy with the corresponding real eigenvalue model, the chGUE, and its non-chiral counterpart, the GUE. It would be very interesting to find an explicit matrix representation of our model, in particular in view of the definition of Dirac mass terms and the corresponding solution.

The structure of RMM with complex eigenvalues seems to be much richer as the number of symmetry classes is much larger than those of real eigenvalue models. While not all of these model may be accessible to the technique of orthogonal polynomials presented here at least the chiral versions of the non-Hermitian or non-symmetric matrices with Dyson index $`\beta =4`$ or $`\beta =1`$, respectively, could be worth investigating. The fact that our chiral model with $`\beta =2`$ again contains the classical polynomials of Laguerre type may be of help.

Acknowledgments: P. Di Francesco and E. Kanzieper are thanked for useful conversation and correspondence as well as P. Forrester and M.L. Mehta for bringing several references to my attention. This work was supported by the European network on “Discrete Random Geometries” HPRN-CT-1999-00161 (EUROGRID).