Welcome to our community

Be a part of something great, join today!

Is there a natural solution?

Hatuk

New member
Jul 21, 2020
2
Hi everyone,
Consider a finite set of positive variables $P = \{x_1,x_2,\ldots, x_n \}$, and a non-strict order on the expressions $\Sigma_{x_i \subseteq P}x_i$. For example:
$$P = \{x_1,x_2,x_3\}$$
$$x_1 + x_2 + x_3 > x_1 + x_2 > x_2 + x_3 > x_1 = x_2 > x_3$$
Can we claim that if there is a solution in which $\forall i,x_i \in \mathbb{R}^+$, there must be a solution in which $\forall i, x_i \in \mathbb{N}^+$?
Thanks!
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,697
You need to consider the equalities and the strict inequalities separately.

Start with the equalities. If there are $d$ of them, they will define an $(n-d)$-dimensional subspace $S$ of $\Bbb{R}^n$, which will have a basis $\{\mathbf{e}_1,\ldots,\mathbf{e}_{n-d}\}$ consisting of rational vectors (vectors with rational coordinates). [In your example, there is just one equality, $x_1 = x_2$. That defines a two-dimensional subspace of $\Bbb{R}^3$, with a basis $\{\mathbf{e}_1=(1,1,0),\mathbf{e}_2=(0,0,1)\}$.]

Every point in $S$ is of the form $\alpha_1\mathbf{e}_1 + \ldots + \alpha_{n-d}\mathbf{e}_{n-d}$, where $\alpha_1, \ldots, \alpha_{n-d}$ are real coefficients. By approximating these coefficients with rational numbers, you see that the rational points in $S$ are dense in $S$.

The strict inequalities in your set, together with the inequalities $x_i>0\ (1\leqslant i\leqslant n)$, define an open subset of $S$. You are told that this subset contains a point $\mathbf{x} = (x_1,\ldots,x_n)$. So by taking a rational point $\mathbf{r}$ in $S$ sufficiently close to $\mathbf{x}$, you can find a rational solution to the problem.

Finally, by multiplying $\mathbf{r}$ by the least common multiple of the denominators of all its coordinates, you get an integer solution to the problem.
 

Hatuk

New member
Jul 21, 2020
2
Thanks!