Compiling self-referential forms

Question

Fix $1\leq d\in\mathbb{N}$ and set $D:=\{0,1,\ldots,d-1\}$. Consider the system of equations \begin{equation} x_i=c_i + \sum_{j\in D}\delta_{x_j,i} \end{equation} with $c_i\in D$ given and $x_i\in D$ unknown for $i\in D$. $\delta_{i,j}=\left\{\begin{array}{ll}1, & i=j \\ 0, & i\not= j\end{array}\right.$ denotes the Kronecker symbol.

Question.

Characterize those $c=(c_i)_{i\in D}$ for which the above equation has a (unique) solution $x=(x_i)_{i\in D}$.

One can obviously use computers to answer this question for small $d$. This is not what I am after. The question might very well be hard. In that case I am also interested in partial results that cover the case $d=10$.

Background.

One can show that \begin{equation} \sum_{i\in D} x_i =\sum_{i\in D} c_i + d \end{equation} and \begin{equation} \sum_{i\in D} i x_i =\sum_{i\in D} i c_i+\sum_{i\in D} c_i + d. \end{equation} These constraints suffice to show that there are no solutions for $d=2$ and that in case $d=3$ the only 4 possible solutions are \begin{equation} c=\left(\begin{array}{c}1\\0\\0\end{array}\right),x=\left(\begin{array}{c}1\\2\\1\end{array}\right) \mbox{ or } x=\left(\begin{array}{c}2\\0\\2\end{array}\right) \end{equation} or \begin{equation} c=\left(\begin{array}{c}1\\1\\0\end{array}\right),x=\left(\begin{array}{c}1\\2\\2\end{array}\right) \end{equation} or \begin{equation} c=\left(\begin{array}{c}2\\0\\0\end{array}\right),x=\left(\begin{array}{c}2\\1\\2\end{array}\right). \end{equation} The above constraints can also be use to put some mild constraints on $c$ and $x$ like \begin{equation} \sum_{i\in D}c_i\leq d(d-2) \end{equation} and \begin{equation} x_i \leq c_i+ \frac{\sum_{j\in D} c_j + d}{i} \end{equation} for $0<i\in D$. To answer the question one probably needs more sophisticated tools from additive number theory or combinatorics.

Motivation.

The motivation for such equations originally stems from the compilation of self-referential forms (cf. the bounty question https://math.stackexchange.com/questions/464868/does-there-exist-a-general-solution-of-this-counting-numbers-game/484663#484663). The above remarks imply that you can compile the form

---

Date: 0.

This form contains ___ zeros.

This form contains ___ ones.

This form contains ___ twos.

---

as

---

Date: 0.

This form contains 1 zero.

This form contains 2 ones.

This form contains 1 two.

---

or

---

Date: 0.

This form contains 2 zeros.

This form contains 0 ones.

This form contains 2 twos.

---

However, compiling

---

Date: 2.

This form contains ___ zero.

This form contains ___ ones.

This form contains ___ two.

---

is not possible.

Answer 1

Some thoughts:

(1) Let $X=(X_{i,j})_{0\leq i,j\leq d-1}$ be a $\{0,1\}$-matrix, where $X_{i,j}=1$ iff $x_i=j$ (in other words, $X_{ij}=\delta_{x_i,j}$). Then $$(x_0,\dots,x_{d-1})^T = X\cdot U,$$ where $U=(0,1,\dots,d-1)^T$, and the original system of equations translates into: $$(\star)\qquad X\cdot U = C + X^T\cdot I,$$ where $C=(c_0,\dots,c_{d-1})^T$ and $I=(1,1,\dots,1)^T$. Additionally, the matrix $X$ satisfies the equation $X\cdot I=I$ (i.e., $I$ represents an eigenvector with the eigenvalue 1 for $X$).

The two properties from the Background section can be easily obtained from $(\star)$ by multiplying it from left by $I^T$ and $U^T$, respectively.

(2) For a given vector $C$, the above matrix equations can be solved for $X_{ij}$ with boolean programming.

(3) For small $d$, trying all possible values of $x_i$, one can find all vectors $C$ that admit solutions and those with unique solutions. I've got the following counts for such $C$ for $d=1,\dots,10$:

soluble: $$0, 0, 3, 47, 631, 9802, 175963, 3613189, 83675571, 2160596196$$

uniquely soluble: $$0, 0, 2, 38, 490, 7380, 128623, 2574962, 58368362, 1480638120$$

(4) It may be interesting also to study those $C$ that admit large number of different solutions. For example, for $d=10$, the maximum number of solutions is 33 and it is attained with $C=(3, 4, 0, 0, 1, 2, 4, 5, 6, 8)^T$.

(5) From the Motivation context, it is clear why $c_i\geq 0$. However, from the equation perspective, this restriction does not look natural. It may be worth to consider the same equation for any integer values of $c_i$.