6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I like your approach. It seems to indicate that there are no more "easy" constraints besides the two mentioned. My first thoughts on the data was that the fraction of unique solvables among solvables is relatively high (>2/3). Another thought was, that we maybe could get some necessary conditions on c by plotting the number of solutions over sum c_i. $\endgroup$ – Uwe Stroinski Jan 30 '15 at 14:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.