Additive function on a module

145 Views Asked by At

Let $v_1, \dots, v_k$ be some non-zero vectors of zeros and ones (in $V^n$ over $\mathbb{R}$, with some fixed basis), such that for every $v_i$ there exist some $1 \leq j_1 \leq \dots \leq j_s \leq k$ and $q > 0$ such that $v_i + v_{j_1} + \dots + v_{j_s} = q\overline{\mathbf{1}}$ (where $\overline{\mathbf{1}}$ is the vector of all ones).

Let's call a vector $a = (a_1, \dots, a_n)$ $\textit{positive}$ if it is not zero and $a_i \geq 0\ \forall i$.

Let $M$ be the module over $\mathbb{Z}$ generated by $v_1, \dots, v_k$ and $f\colon M \rightarrow \mathbb{R}$ a function, such that:

  • $f(\sum k_i v_i) = \sum k_i f(v_i)$,
  • $f(q\overline{\mathbf{1}}) = q$
  • if $a$ is positive then $f(a) > 0$.

Can we say that there is some $\epsilon > 0$, such that $f(a) > a_i \epsilon$ for every positive vector $a = (a_1, \dots, a_n)$ in $M$ and every $1 \leq i \leq n$?

1

There are 1 best solutions below

0
On

Ok, let me try to answer my own question and maybe someone can validate the solution.

I'll say $(a_1, \dots, a_n) \geq (b_1, \dots, b_n)$ if $a_i \geq b_i$ for all $1 \leq i \leq n$. I claim, there is a finite subset of positive vectors $P \subset M$, such that for any positive $a \in M$ there is some $p \in P$ such that $a \geq p$. I prove this by induction: assume $(n-1)$ coordinates except for the i-th one have some fixed values $x_1, \dots, x_{n-1}$. For such vectors one can easily find the finite set with the required property: it is either empty (if there is no such positive vectors) or contains the one vector with minimal i-th coordinate among them. Assume this is true for any $(n-(k-1))$ fixed coordinates, and let $i_1, \dots, i_{n-k}$ be fixed to some $x_1, \dots, x_{n-k}$. If there is no such vectors, again take an empty set. Otherwise, let $b = (b_1, \dots, b_n)$ be such a vector. For every $i$-th coordinate that is not fixed and for every integer $0 \leq x < b_i$ I build, by the inductive assumption, a finite set $P_i^x$ with coordinates $i, i_1, \dots, i_{n-k}$ fixed to $x, x_1, \dots, x_{n-k}$. Now I take $P = \{b\} \cup \bigcup P_i^x$. $P$ is finite and if some positive $a \ngeq b$ then there is at least one coordinate $0 \leq a_i < b_i$, thus there is $p \in P_i^{a_i}$ such that $a \geq p$.

Now it follows that every positive vector $a$ can be represented as $a = \sum_{p \in P} k_p p$ where all $k_p \in \mathbb{N}$. Indeed, since there is some $p \in P$ such that $a \geq p$ then $(a-p)$ is zero or positive and has at least one coordinate smaller than $a_i$ (since $p$ is positive). If it is not zero, we can apply the same procedure to it and in a finite number of steps get to the zero vector.

Let $P_i \subseteq P$ be the subset with $p_i \neq 0$ (it's never empty since the positive vector $q\overline{\mathbf{1}} \in M$ for some $q > 0$ and can be represented as the sum above). Now I take $\epsilon_i = \min_{p \in P_i} \frac{f(p)}{p_i}$ and $\epsilon = \frac{1}{2} \min_{i=1}^n \epsilon_i$. Obviously $\epsilon > 0$.

If $a$ is positive then: $f(a) = \sum_{p \in P} k_p f(p) \geq \sum_{p \in P_i} k_{p_i} f(p_i) \geq \sum_{p \in P_i} k_{p} {p_i} \epsilon_i > (\sum_{p \in P_i} k_p p_i) \epsilon = a_i \epsilon$.