-1
$\begingroup$

What are the subsets $V\subseteq\mathbb{Z}^n$ such that there is an integer combination of vectors in $V$ equal to $(1, 1, 1, \ldots)$? (where $n \in \mathbb{Z}^+$ and $\mathbb{Z}^n$ is the n-ary Cartesian product over $\mathbb{Z}$)

By integer combination I mean a positive integer $p$ along with vectors $v_1,v_2,\ldots,v_p \in V$ and integers $z_1,z_2,\ldots,z_p$ such that $z_1v_1 + z_2v_2 + \cdots + z_pv_p = (1,1,1,\ldots)$ with componentwise multiplication and addition.

  • 1
    Please clarify what you mean by "integer combination".2012-05-04
  • 0
    Given a finite subset of $\mathbb{Z}^n$ (and the span of any set is contained in the span of a subset of size at most $n$), you can use straighforward methods (e.g., parts of the algorithm to find the Smith Normal Form) to find a basis for the submodule they generate. Once you have a basis, determining whether $(1,1,\ldots,1)$ is in the span is straighforward. But giving an abstract description is likely to be difficult.2012-05-06
  • 0
    Well, I can do the case $n=1$; you want the subsets $A$ such that there is no $d\gt1$ dividing every element of $A$.2012-05-06
  • 0
    The way you've currently phrased the question, with an $A$ and a $V$, the answer is that none exist. $V=\emptyset$ is always a subset of any $A$, and this $V$ doesn't have the property you seek. Carefully chosen nonempty sets would almost always work too. - If you just mean that $A$ has this property, then you're asking whether the subgroup generated by $A$ contains $(1,\dots,1)$; in this case, @ArturoMagidin's answer applies.2012-05-06
  • 0
    @Greg and Gerry: I think you both misread the question. $A$ is a subset of $\mathcal P(\mathbb Z^n)$, not of $\mathbb Z^n$, and $V$ is an element of $A$ and a subset of $\mathbb Z^n$, not a subset of $A$. Of course Gerry's comment still applies if you replace $A$ by $V$. The formulation of the question is unnecessarily complicated; it would be simpler to just ask about the subsets $V\subseteq \mathbb Z^n$ with this property.2012-05-06
  • 0
    Well, thanks anyway all.2012-05-06

1 Answers 1