# Constructing a vector consisting of nonnegative entries

Consider constructing a vector $$v=(a_1,a_2,\ldots,a_n)$$ consisting of nonnegative integers such that $$a_1=1$$ and, if $$a_j$$'s are nonzero, then $$a_j\equiv a_{n-j+2}+j-1 \pmod m\ \forall 1, where $$m$$ is the number of nonzero entries; with the additional constraint that all nonzero $$a_i$$'s are distinct modulo $$m$$. 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? I think this should be possible if $$m$$ is odd. For example, $$(1,4,2,5,3)$$ and $$(1,4,2,0,0,5,3)$$ are such vectors. It is easy to construct if the first entries (within $$\lfloor\frac{n}{2}\rfloor$$) of the vector are consecutive. But, in other cases, it is not clear as to how to proceed with the construction. Any hints? Thanks beforehand.

• Your two examples are nonnegative, have $a_1=1$, and have distinct nonzero entries, but the mod condition fails for both. – RobPratt Feb 8 at 22:24
• @RobPratt thanks! edited. see now. – vidyarthi Feb 8 at 22:29
• Still not right. For $j=2$, $4\not\equiv 5+2-1 \pmod 5$. – RobPratt Feb 8 at 22:37
• For the first example, $n=5$, and $j=2$ yields $a_{n-j+1}=a_{5-2+1}=a_4=5\not= 3$. – RobPratt Feb 8 at 23:43
• Your second example fails for $j=6$ because $5\not\equiv 2+6-1 \pmod{5}$. – RobPratt Feb 9 at 18:39

Yes, such construction is always possible.

Consider two sets of pairs of values: $$\big\{ (2+t,m-t)\quad :\quad t=0\,..\,\lfloor\frac{m-1}{4}\rfloor-1\big\},$$ where differences of elements modulo $$m$$ are: $$2,4,\dots,2\cdot\lfloor\frac{m-1}{4}\rfloor$$, and $$\big\{ (\lfloor\frac{m+1}{2}\rfloor+t+1,\lfloor\frac{m+1}{2}\rfloor-t)\quad :\quad t=0\,..\,\lfloor\frac{m+1}{4}\rfloor-1\big\},$$ where differences of elements modulo $$m$$ are: $$1, 3, \dots, 2\cdot\lfloor\frac{m+1}{4}\rfloor-1.$$ Together they give all differences from $$1$$ to $$\lfloor\frac{m-1}{2}\rfloor$$.

Notice that all elements forming pairs in these sets are $$\ne0,1$$ and are distinct modulo $$m$$.

Therefore, it's enough to assign the values from these sets to the corresponding pairs $$(a_j,a_{n+2-j})$$, giving $$2\cdot\lfloor\frac{m-1}{2}\rfloor$$ nonzero $$a_j$$'s. If $$m$$ is even we need to assign one more yet unassigned nonzero value (which is $$\lfloor\frac{3m}{4}\rfloor+1$$) to any of yet unassigned $$a_j$$ with $$j>\frac{n}2$$. The other unassigned $$a_j$$ are set to zero.

• @vidyarthi: a lot of drawing on a piece of paper ;) – Max Alekseyev Feb 10 at 21:23
• @vidyarthi: I drew matchings between residues modulo $m$ giving differences $1,2,\dots$ – Max Alekseyev Feb 10 at 21:26
• Assume $m|n$. There are no $j\equiv 1\pmod m$ in the interval $[2,n/2]$ if $m\geq n/2$. So, the additional restriction playa role only when $m\leq n/3$. However, in this case we can simply assign all nonzero values to $a_j$'s with $j>n/2$. – Max Alekseyev Feb 22 at 6:04
• For $m\leq n/3$, simply set $a_{n/2+k}=k$ for $k=1..m$, and all other $a_j$ to 0. If $n/3<m<n/2$, then $m$ cannot divide $n$. – Max Alekseyev Feb 22 at 22:11
• I do not quite follow again. According to your original question, the congruence $a_j\equiv a_{n+2-j}+j-1\pmod m$ is required only for nonzero $a_j$. In the above example, for $j=n/2-1$ we have $a_j=0$, and so the congruence may not hold. – Max Alekseyev Feb 24 at 13:49

Computational experiments for $$1 \le m \le n \le 20$$ yield feasible solutions even if you impose the upper bound $$a_j \le n$$. Here is an infinite family for $$m \le \lceil n/2\rceil +1$$: $$(1,\underbrace{0,\dots,0}_{n-m},2,3,4,\dots,m)$$

Here are the lexicographically smallest solutions for $$n=m$$: $$\begin{matrix} n & a\\ \hline 1& (1)\\ 2& (1, 2)\\ 3& (1, 2, 3)\\ 4& (1, 3, 4, 2)\\ 5& (1, 3, 4, 5, 2)\\ 6& (1, 3, 6, 5, 4, 2)\\ 7& (1, 3, 6, 5, 7, 4, 2)\\ 8& (1, 3, 6, 8, 7, 5, 4, 2)\\ 9& (1, 3, 6, 8, 7, 9, 5, 4, 2)\\ 10& (1, 3, 6, 10, 9, 8, 5, 7, 4, 2)\\ 11& (1, 3, 6, 8, 11, 9, 10, 7, 5, 4, 2)\\ 12& (1, 3, 6, 11, 9, 12, 10, 7, 5, 8, 4, 2)\\ 13& (1, 3, 6, 8, 13, 12, 10, 11, 7, 9, 5, 4, 2)\\ 14& (1, 3, 6, 10, 12, 14, 5, 11, 13, 9, 8, 7, 4, 2)\\ 15& (1, 3, 6, 8, 14, 12, 15, 11, 13, 9, 7, 10, 5, 4, 2)\\ 16& (1, 3, 6, 10, 12, 16, 15, 5, 13, 14, 9, 11, 8, 7, 4, 2)\\ 17& (1, 3, 6, 8, 13, 15, 17, 14, 12, 16, 7, 11, 10, 9, 5, 4, 2)\\ 18& (1, 3, 6, 8, 13, 16, 18, 17, 15, 14, 7, 10, 12, 11, 9, 5, 4, 2)\\ 19& (1, 3, 6, 8, 11, 17, 19, 16, 18, 14, 15, 10, 9, 13, 12, 7, 5, 4, 2)\\ 20& (1, 3, 6, 8, 13, 17, 20, 18, 15, 19, 16, 10, 7, 11, 14, 12, 9, 5, 4, 2)\\ \end{matrix}$$

• thanks, but what about the general case? And even in the cases you have provided, what happens when I introduce zeroes in between the numbers ( thereby increasing $n$ keeping $m$ fixed) ? – vidyarthi Feb 9 at 21:35