Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs

Question

This might be related to counting hamiltonian cycles.

@Peter Taylor gave negative result about the one dimensional case, but we believe his attack is not directly applicable to this question.

Given positive integer $n$, find integer $m$ and $m \times n$ matrix $A = a_{i,j}$ with positive integer entries.

Let $y_1,...,y_n$ be integer variables.

Consider the following integer program with constraints:

• $0 \le y_i \le n$
• $\sum_{j=1}^n y_j = n$
• For $ 1 \le i \le m$: $\sum_{j=1}^n y_j a_{i,j}= \sum_{j=1}^n a_{i,j}$

We require the integer program to have unique solution of $y_i$ all ones for chosen $(m,A)$. Let the solution be $(m_0,A_0)$.

Q1: How small the unique solution can be in terms of $n$? Can we get $2^{m_0} \max ( a \in A_0)=\exp(o(n))$?

Getting $O(\exp(n))$ is easy by taking $m=1,a_{1,i}=2^i$.

Answer 1

Yes, we can get $\exp(\omicron(n))$.

Assume for a moment that $n$ is a perfect square and $m=\sqrt{n}$. The general case is essentially the same, just a bit more complicated. The idea is to partition those $n=m^2$ variables $y_1,\ldots\, y_n$ in $m$ blocks of $m$ digits in base $b=n+1$. Define

$$a_{ij} = \left\{ \begin{array}{ll} b^{\,j-m(i-1)-1} & \text{if } \; m(i-1) \lt j \leq mi \\ 0 & \text{otherwise} \end{array} \right. $$

For example if $n=9$ we have $m=3$ and $b=10$ and

$$ A = \left( \begin{array}{rrr|rrr|rrr} 1 & 10 & 100 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 10 & 100 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 & 100 \\ \end{array} \right) $$

It is not hard to see that such $A$ only admits the trivial solution where all the $y_j$ are equal to $1$, because $0 \le y_j \lt n + 1 = b$.

Now $\max a_{ij} = b^{m-1} \le b^m$ and thus

$$ 2^m \cdot \max a_{ij} \le 2^m b^m = (2b)^m = \exp(m \, \ln(2b)) = \exp(\sqrt{n} \,\ln(2n+2)) $$

and $\sqrt{n} \,\ln(2n+2)$ is in $\omicron(n)$.

The question actually asked for positive integer entries $a_{ij}$ rather than just non-negative entries. But because $\sum_{j=1}^n y_j = n$, we can instead use $a'_{ij} = a_{ij} + 1$, and since $\,\max a'_{ij} = b^{m-1} + 1 \le b^m$ we arrive at the same bound.

Edit (based @joro's comment) In summary, we have $\sqrt{n}$ equations with $\max a_{ij} \sim n^{\sqrt{n}}$.

Answer 2

Below I show that $m$ cannot be constant.

The given system of $m$ equations can be reduced to the case of $m=1$, that is, to a single equation: $$\sum_{j=1}^n y_j a'_{j} = \sum_{j=1}^n a'_{j}$$ where $a'_{j} := \sum_{i=1}^m a_{ij}b^{i-1}$ with $b:=n\cdot \max a_{ij}+1$. The key observation is that both sides of each equation $$\sum_{j=1}^n y_j a_{ij} = \sum_{j=1}^n a_{ij}$$ is less than $b$ (under the constraint $\sum_j y_j=n$).

Then, by the negative result of Peter Taylor, we have $$\frac{(n\cdot\max a_{ij} + 1)^m}{n} > \max a_{ij}\cdot \frac{b^m-1}{b-1} \geq \max a'_{j} \in \Omega( n^{-3/2} 2^n ),$$ implying that $\max a_{ij} \in \Omega( n^{-1-1/(2m)} 2^{n/m} )$, which would contradict the given asymptotic bound if $m$ is constant.