13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Then I get something different for n=6 (quantity is the same, it's 4, but tuples are different). First, [0,5,10] and [0,2,7] are cyclic shifts of each other: [0,2,7]+10=[10,0,5] ($\mod12$ ). On the other hand, interesting must be also [0,2,4,7,9] (which up to cyclic shifts is the same as [0,2,5,7,9], [0,2,5,7,10], [0,3,5,7,10], or [0,3,5,8,10]). For n=7 I get the same result. The numbers up to 12 I get are 0,0,1,1,3,4,9,15,38,80,197,461, does this match with your calculations? $\endgroup$ – მამუკა ჯიბლაძე Dec 27 '16 at 19:06
  • 1
    $\begingroup$ There are some patterns if counting configurations with fixed numbers of black points, but the whole thing seems to be quite complicated.$$\begin{array}{rrrrrrrrrrr} 1\\0&1\\1&0&2\\0&1&1&2\\1&1&3&1&3\\0&1&4&4&3&3\\1&1&6&11&10&5&4\\0&2&6&18&26&14&10&4\\1&1&11&23&59&56&27&14&5\\0&2&10&36&87&144&113&42&22&5\end{array}$$ $\endgroup$ – მამუკა ჯიბლაძე Dec 27 '16 at 20:45
  • 1
    $\begingroup$ I have to optimize my code first, the way it is now it will certainly choke beyond 14. A couple of observations: if you take an interesting configuration for $n$ and insert after any black point one white and one black point, you obtain an interesting configuration for $n+1$. Thus certain amount of configurations can be accounted for from previous ones. This is not much, but... $\endgroup$ – მამუკა ჯიბლაძე Dec 27 '16 at 21:49
  • 1
    $\begingroup$ Hm, might well be - it has to do with necklaces :D The second observation I promised: if you take an interesting configuration with $g>2$ for $n$ and insert after a black point three white and one black point, you get an interesting configuration for $n+2$, but there is one exception: the configuration with consecutive distances between nearest black points 3,3,...,3,3,4 is not interesting, although the one with distances 3,3,...,3,3 is. There may be similar constructions, maybe ultimately generating everything from the configurations [0,2k-1] (for n=2k-1). $\endgroup$ – მამუკა ჯიბლაძე Dec 27 '16 at 22:39
  • 1
    $\begingroup$ The minimal distance is by the way also a famous homological dimension when interpreting those configurations as algebras. Namely the dominant dimension. $\endgroup$ – Mare Dec 27 '16 at 22:52

Your Answer

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

Browse other questions tagged or ask your own question.