System of equations over $\mathbb{Z}_{2^n}$ with conditions

96 Views Asked by At

During my research I stumbled upon this system over $\mathbb{Z}_{2^n}$. Let $k=2^{n-1}-1$ then the system looks like \begin{equation*} \begin{cases} x_1+2^{n-1}=d_k +x_k \\ x_2+2^{n-1}=d_1+x_1 \\ x_3+2^{n-1}=d_2+x_2 \\ \tag{1} \dots \\ x_k+2^{n-1}=d_{k-1}+x_{k-1} \\ x_i \notin \{x_j,x_j + 2^{n-1}\}, i \neq j \\ d_i \notin \{d_j,-d_j\}, i \neq j, \end{cases} \end{equation*} where '+' means addition in $\mathbb{Z}_{2^n}$ and $x_i,d_i$ are variables for i $\in \overline{1,k}$. I've noticed, that system (1) without any conditions has solutions iff $d_1+d_2+\dots+d_k=2^{n-1}$, so my idea was to fix $d_1,d_2,\dots d_k$ and then the solution to the system without coniditons looks like \begin{equation} \begin{cases} x_1=d_k +2^{n-1} \\ x_2=d_k+d_1 \\ x_3=d_k+d_1+d_2 +2^{n-1} \\ \tag{2} \dots \\ x_{k-1}=d_k+d_1+\dots +d_{k-2} \\ x_k=2^{n-1}. \end{cases} \end{equation} Now, let $c_i=d_i+2^{n-1}$, then if $d_i \notin \{d_j,-d_j\}, i \neq j$ it follows that $c_i \notin \{c_j,-c_j\}, i \neq j$. Then in terms of $c_i$ solution (2) look like \begin{equation} \begin{cases} x_1=c_k \\ x_2=c_k+c_1 \\ x_3=c_k+c_1+c_2 \\ \tag{3} \dots \\ x_{k-1}=c_k+c_1+\dots +c_{k-2} \\ x_k=0. \end{cases}. \end{equation} So, solving of system (1) is equivalent to finding $c_1,\dots ,c_k$, such that $c_i \notin \{c_j,-c_j\}, i \neq j$ and all sums like $c_i+\dots +c_j, 1 \leq i \leq j \leq k-2$ are nonzero modulo $2^{n-1}$. I've programmed it and was able to find some interesting candidates for $C=\{c_i\}$. It is $C=\{1,2,\dots,2^{n-2}-1,2^{n-1},2^{n-1}+1,\dots,2^{n-1}+2^{n-2}\}$ as for $n=4$ we have solutions like $(c_1,c_2,\dots,c_7)=(3, 2, 1, 9, 10, 11, 12)$
$(c_1,c_2,\dots,c_7)=(1, 2, 3, 12, 11, 10, 9)$ and a couple of others.
For $n=5$ we have something like $(c_1,c_2,\dots,c_{15})=(24, 19, 20, 18, 21, 22, 17, 23, 1, 2, 3, 4, 5, 6, 7)$ $(c_1,c_2,\dots,c_{15})=(1, 6, 23, 4, 19, 7, 24, 21, 22, 20, 3, 18, 2, 17, 5)$.
For $n=6$ my program unfortunately wasn't able to find any. So the question is, how to find solutions to (1) for any $n \in \mathbb{N}$ or at least prove its existence? Maybe there are other ways much simplier ways to solve (1) rather than mine? I'll appreciate any help.