
> 
> Here is the short version of the combinatorial problem:
> 
> 
> Given a positive integer $n \geq 2$. Draw a circle with $2n$ points indexed by the numbers from $\mathbb{Z}/ 2n \mathbb{Z}$. We colour the points black and white and assume that there is at least one black point. Since the problem is invariant under rotation of the circle we can assume that the point 0 is black. Let $x\_0=0< x\_1 < x\_2 < ... <x\_r$ be the black points (corresponding to numbers in $\mathbb{Z}/ 2n \mathbb{Z}$) and assume always that there are no neighboring black points, meaning that $x\_i \neq x\_j \pm 1$ for all $i,j$.
> 
> 
> Define the Gorenstein dimension $g$ of such a configuration as the maximal distance between two black points such that only white points are between them.
> 
> 
> Call such a configuration interesting in case the following is true: There exist numbers $p,q$ with $p+q \frac{(-1)^{x\_j+i+1}+1}{2}-[\frac{x\_j+i+1}{2}] \neq 0$ mod $n$ for all $i=1,2,...,g-1$ and all $j$. Here [ ] denotes the floor function.
> 
> 
> **Main problem**: Enumerate the interesting configurations (up to rotation or not).
> 
> 
> 


**More information:**


I translated a representation theoretic/homological problem into elementary combinatorics/number theory problem. I expected an easy solution but I can not really see what is behind that. So I pose the elementary problem here. (See the end of the post for the representation theoretic/homological background.)


**Elementary formulation:**


Given a positive integer $n \geq 2$. Draw a circle with $2n$ points indexed by the numbers from $\mathbb{Z}/ 2n \mathbb{Z}$. We colour the points black and white and assume that there is at least one black point. Since the problem is invariant under rotation of the circle we can assume that the point 0 is black. Let $x\_0=0< x\_1 < x\_2 < ... <x\_r$ be the black points (corresponding to numbers in $\mathbb{Z}/ 2n \mathbb{Z}$) and assume always that there are no neighboring black points, meaning that $x\_i \neq x\_j \pm 1$ for all $i,j$. We can write such configurations uniquely by indicating what $n$ is and which points are black.


For example: $n=4$ and the configuration is $[0,3,6]$, meaning that it is a circle with 8 points such that the points 0,3 and 6 are black and the others are white.


Define the Gorenstein dimension $g$ of such a configuration as the maximal distance between two black points such that only white points are between them. In the example $[0,3,6]$, the Gorenstein dimension is equal to 3.
Call such a configuration interesting in case the following is true: There exist numbers $p,q$ with $p+q \frac{(-1)^{x\_j+i+1}+1}{2}-[\frac{x\_j+i+1}{2}] \neq 0$ mod $n$ for all $i=1,2,...,g-1$ and all $j$. Here [ ] denotes the floor function. Here are the interesting configurations for $2 \leq n \leq 7$:


-n=2: none


-n=3:[0,3]


-n=4:[0,3,6]


-n=5:[0,5],[0,2,5,8],[0,3,5,8]


-n=6:[0,3,6,9],[0,2,4,7,10],[0,5,10],[0,2,4,7,9]


-n=7:[0,7], [0,5,10], [0,2,7,12], [0,5,7,12], [0,4,7,11], [0,3,6,9,12], [0,2,4,6,9,12], [0,2,4,7,9,12], [0,2,5,7,9,12].


I can not really see a pattern but maybe it is better to look (and count) at those configurations not up to rotation?


So the main question is as follows:



> 
> Is there a nice characterisation of interesting configurations? What is their number up to (or not up to) rotation? Is there a closed formula?
> 
> 
> 


I can for example prove that if all $x\_i$ are even, the configuration is never interesting.


**Representation theoretic /homological background:**


This decides whether a representation-finite gendo-symmetric biserial algebra has finitistic dominant dimension equal to the Gorenstein dimension or equal to the Gorenstein dimension +1 (there can be only those two possibilities). See the paper <https://arxiv.org/abs/1607.05965> for such algebras, which generalise the classical Brauer tree algebras.


A configuration is interesting iff the corresponding algebra has finitistic dominant dimension equal to the Gorenstein dimension +1. (Of course there might be a more clever way than translating the problem into combinatorics/number theory.)


edit: Here is the example of $n=2$ and configuration [0,2]: Then $x\_0=0$ and $x\_1=2$ and $g=2$. So there are two conditions: ($i=g-1=1$) $p+q-1 \neq 0 \mod 2$ and $p+q-2 \neq 0 \mod 2$. Clearly no $(p,q)$ exists satisfying both conditions.



Special configurations on a circle from a homological algebra problem
There is a simple characterization of interesting configurations:


**Lemma.** A configuration $x\_0=0< x\_1 < x\_2 < ... <x\_r$ of Gorenstein dimension $g$ is *interesting* if and only if there exist indices $i,j$ such that $x\_i$ is even, $x\_j$ is odd, and
$$x\_{i+1} - x\_i \equiv x\_{j+1}-x\_j \equiv g\pmod{2n},$$
where the indices are considered modulo $r+1$.


We can also specify particular values of $p,q$ that will do the job:
$$(p,q) = \begin{cases}
\big(-\frac{x\_{j+1}}2, \frac{x\_j - x\_i - 1}2\big), & \text{if $g$ is odd};\\
\big(-\frac{x\_{i+1}}2, \frac{x\_i - x\_j - 1}2\big), & \text{if $g$ is even}.
\end{cases}$$




---


Let's now enumerate the interesting configurations for given $n$ and $g$.


We find it convenient to employ the transfer-matrix method by viewing each configuration as a closed walk in the algebraically weighted digraph $G$ on two nodes: `Even` and `Odd` corresponding to the parities of black points. We will need to keep track of: the number of black points, their total span (which should be $2n$ at the end), and of the number of steps of length $g$ taken from each of the nodes (each should be at least 1). These quantities will be accounted as the powers of indeterminates $x, y,z,t$.
Correspondingly, $G$ has the following arcs:


* `Even` to `Even` of weight
$$y^2 + y^4 + \dots + y^{2\lfloor (g-1)/2\rfloor} + [g\text{ is even}]\cdot zy^g= y^2\frac{1-y^{2\lfloor (g-1)/2\rfloor}}{1-y^2} + [g\text{ is even}]\cdot zy^g;$$
* `Odd` to `Odd` of weight
$$y^2 + y^4 + \dots + y^{2\lfloor (g-1)/2\rfloor} + [g\text{ is even}]\cdot ty^g= y^2\frac{1-y^{2\lfloor (g-1)/2\rfloor}}{1-y^2} + [g\text{ is even}]\cdot ty^g;$$
* `Even` to `Odd` of weight
$$y^3 + y^5 + \dots + y^{2\lfloor g/2\rfloor-1} + [g\text{ is odd}]\cdot zy^g= y^3\frac{1-y^{2\lfloor (g-2)/2\rfloor}}{1-y^2} + [g\text{ is odd}]\cdot zy^g;$$
* `Odd` to `Even` of weight
$$y^3 + y^5 + \dots + y^{2\lfloor g/2\rfloor-1} + [g\text{ is odd}]\cdot ty^g= y^3\frac{1-y^{2\lfloor (g-2)/2\rfloor}}{1-y^2} + [g\text{ is odd}]\cdot ty^g.$$


Consider matrix $M:=(I\_2-xA)^{-1}$, where $A$ is the adjacency matrix of $G$ and $I\_2$ is the $2\times 2$ identity matrix. Let $f\_e(x,y,z,t):=M\_{1,1}$ and $f\_o(x,y,z,t):=M\_{1,2}$, and further define
$$F\_g(x,y) := f\_e(x,y,1,1) - f\_e(x,y,1,0) - f\_e(x,y,0,1) + f\_e(x,y,0,0) +
f\_o(x,y,1,1) - f\_o(x,y,0,0).$$
For example, for even $g$, we have
$$F\_g(x,y) = \frac{{\left(2 \, x y^{2} - x y^{g + 2} - x y^{g} + 2 \, y^{2} - 2\right)} {\left(y^{g-2}-1\right)} x^{2} y^{g + 3}}{{\left(x^{2} y^{4} - x^{2} y^{g + 2} - 2 \, x y^{2} + x y^{g + 2} + x y^{g} - y^{2} + 1\right)} {\left(x y^{2} - x y^{g + 1} + y - 1\right)} {\left(x y^{2} - x y^{g} - y - 1\right)}}$$
and there is a similar expression in the case of odd $g$.


Then the number of interesting configurations with $k$ black points equals $[x^ky^{2n}]\ F\_g(x,y)$, and without fixing $k$ (ie. summing over all $k$) it is $[y^{2n}]\ F\_g(1,y)$. Up to rotation, the number of interesting configurations with $k$ black points equals
$$\frac1k \sum\_{d\mid \gcd(2n,k)} \phi(d)\cdot [x^{k/d}y^{2n/d}]\ F\_g(x,y),$$
where $\phi(\cdot)$ is Euler's totient function.


