Construction of a vector consisting of entries with a peculiar pattern

Question

Note: A similar problem was asked in this MO post, but no importance was attached to order of nonzero numbers and zeros

Consider constructing a $n$-tuple of numbers $v=(a_1,a_2,\ldots,a_n)$ consisting of nonnegative integers such that it consists of $m$ nonzero entries, $a_1=1$ and, if $a_j$'s are nonzero, then $a_j\equiv a_{n-j+2}+j-1 \pmod m $, ; with the additional constraint that all nonzero $a_i$'s are distinct modulo $m$. The places of the nonzero numbers (the $j$s) and zeros are chosen in a fixed predetermined order. For example, suppose $n=20$, $m=11$ and the order of nonzero numbers is $\{1,*,0,*,*,*,0, *,0,0,0,0,0,*,0,*,*,*,0,*\}$, then we can find the numbers satisfying the congruence as $(1,11,0,8,7,9,0,2,0,0,0,0,0,6,0,4,3,5,0,10)$. If $n=7$, $m=5$, and the order of nonzero numbers and zeros is $\{1,*,*,0,0,*,*\}$, we can find it as $(1,4,2,0,0,5,3)$ Note that the number $m$ itself appears once as a nonzero number satisfying the above congruence.

Is it always possible to construct such a vector for any given $n, m$ and order of nonzero numbers and zeros? I think this should be possible if $m\le n$ is odd. It is easy to construct if the order of nonzero and zeros were consecutive (within $\lfloor\frac{n}{2}\rfloor$) . But, in other cases of nonzero and zero patterns, it is not clear as to how to proceed with the construction. Any hints? Thanks beforehand.

Answer 1

The problem can be posed as a maximum independent set problem.

Let $D$ be the set of values for differences $a_j-a_{n-j+2}$ allowed by the given pattern. Consider a graph $G$ with the vertex set: $$V = \{ (a,b) \in \{2,3,\dots,m\}^2\ :\ ((a-b)\bmod m)\in D \}$$ and two vertices $(a_1,b_1)\ne (a_2,b_2)$ are connected with an edge whenever $\{a_1,b_1\}\cap\{a_2,b_2\}\ne\emptyset$ or $a_1-b_1\equiv a_2-b_2\pmod{m}$.

Let $S$ be the maximum independent set. It is clear that $|S|\leq |D|$. When $|S|=|D|$, $S$ contains exactly one pair $(a,b)$ for each difference from $D$, and these pair are disjoint as sets. Hence, they can be placed to the corresponding positions in the pattern to deliver a solution.

---

Here is a sample SageMath code that for a given $m$ and a difference set $D$, computes the corresponding disjoint pairs of elements.

For a given example with $m=11$ and $D = \{ 1, 3,4,5, 7\}$ it gives the following corresponding disjoint pairs:

{1: (3, 2), 7: (4, 8), 4: (9, 5), 3: (10, 7), 5: (11, 6)}

---

In some cases the problem allows explicit solution. For example, when $D\cap \{ (-d)\bmod m\ :\ d\in D\}=\emptyset$, a solution can be derived from my construction for the previous question.