Condition for existence of certain lattice points on polytopes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T00:50:14Z http://mathoverflow.net/feeds/question/13094 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13094/condition-for-existence-of-certain-lattice-points-on-polytopes Condition for existence of certain lattice points on polytopes Hailong Dao 2010-01-27T03:48:58Z 2011-04-22T19:22:13Z <p>Let $a_1,\cdots, a_n$ be integers such that $a_i\geq 2$ for all $i$ and $k>0$ another integer. </p> <p>I am interested in whether there exist integers $x_1,\cdots, x_n$ with <code>$0&lt;x_i&lt;a_i$</code> satisfying:</p> <p><code>$$\frac{x_1}{a_1}+ \cdots + \frac{x_n}{a_n}=k \ \ (*)$$</code> </p> <p>For example, if $n=2,k=1$, there exist a solution in the specified range iff $\text{gcd}(a_1,a_2) \neq 1$, in other words $\text{lcm}(a_1,a_2)-a_1a_2 \neq 0$.</p> <p><strong>Question</strong>: For what pairs $n,k$ is there a polynomial $F$ whose inputs are $\text{lcm}$ of various subsets of <code>$\{a_i\}_{1\leq i\leq n}$</code> such that (*) has a solution in the specified range if and only if $F\neq 0$ (see some examples I have in mind below)? </p> <p>Some observations: If $k\geq n$ then $F\equiv 0$ works, trivially.</p> <p>Some calculations for small values of $(n,k)$ suggest the following strange function: for each subset <code>$I \subset \{1,\cdots,n\}$</code> define <code>$$f_I(a_1,\cdots,a_n):= \frac{\prod_{i\in I}a_i}{\text{lcm}\{a_i\}_{i\in I}}$$</code></p> <p>For $I=\varnothing$ we set $f_I=1$. Let: </p> <p><code>$$F(a_1,\cdots,a_n):= \sum_{I\subset \{1,\cdots,n\}}(-1)^{|I|}f_I(a_1,\cdots,a_n)$$</code></p> <p>(You can replace $F$ by a polynomial of the $\text{lcm}$s which vanishes at the same time). This works for $(n,k)=(2,1)$ and probably $(3,1)$ (which would imply $(3,2)$). It does <em>not</em> work for $(4,1)$ but seems to work for some sequence with $(n,k)= (4,2)$ (may be the function depends on $n/k$?). Have anyone seen this kind of formula before in other contexts? </p> <p>PS: I am not sure what tags should be used. Please feel free to re-tag.</p> <p>EDIT: Apparently this question is related to existence of lattice points on a polytope. I checked through some of the references pointed to in <a href="http://mathoverflow.net/questions/10266/counting-lattice-points-on-an-n-simplex" rel="nofollow">this question</a> on MO, but could not find the exact answer to what I wanted. </p> http://mathoverflow.net/questions/13094/condition-for-existence-of-certain-lattice-points-on-polytopes/14945#14945 Answer by Ewan Delanoy for Condition for existence of certain lattice points on polytopes Ewan Delanoy 2010-02-10T20:50:55Z 2010-02-11T09:25:56Z <pre><code> I don't know if you're still interested in this problem Hailong, but here is a partial result. I make two natural restrictions : </code></pre> <ul> <li><p>Restriction 1 : avoid small primes. Let $B_n$ denote the (infinite) set of integers all of whose prime factors are $>n$. I assume that the all the $a_i$ are in $B_n$ (this is to avoid the difficulty that for example when $n=3$ and $k=1$, (*) has a solution when $a_1=a_2=a_3=p$ for $p$ a prime $>2$ , but not when $a_1=a_2=a_3=2$ ).</p></li> <li><p>Restriction 2 : avoid small $k$. I assume that $k \geq \frac{n}{2}$ (this is to avoid the difficulty that for example when $n=4$ and $a_1=a_2=2,a_3=a_4=3$, (*) has a solution for $k=2$ but not for $k=1$). Under those restrictions, the following conditions are equivalent :</p></li> </ul> <p>(i) (*) has a solution in the desired range. (ii) No $a_i$ is prime to all the others $a_j$. (iii) The polynomial $F=\prod_{i=1}^{n}G_i$ is nonzero, where $G_i$ is the polynomial $\sum_{j\neq i}(a_ia_j-\text{lcm}(a_i,a_j))$.</p> <pre><code>Note that the polynomial is independent of $k$. </code></pre> <p>The only difficult implication is $(ii) \rightarrow (i)$. To show this, consider the undirected graph $G$ whose vertices are the integers from $1$ to $n$ and such that there is an edge joining $i$ to $j$ iff $gcd(a_i,a_j)>1$. Then condition (ii) says that $G$ is connected. By a straightforward graph-theoretic lemma, there is a subgraph of $G$ which is a disjoint union of stars. Thus, we can write $\lbrace 1,2, \ldots n\rbrace$ as a disjoint union $A_1 \cup A_2 \cup \ldots \cup A_t (t \geq 1)$ such that for each $l$ between $1$ and $t$ we have $|A_l| \geq 2$ and there is a distinguished vertex $u_l$ in $A_l$ that is connected to all the other vertices in $A_l$. Restriction 2 ensures that we can find a decomposition $k=\sum_{l=1}^{t}\alpha_l$ where each $\alpha_l$ is an integer with $0&lt;\alpha_l &lt; |A_l|$. Restriction 1 ensures that we may find, for each $l$ $(x_i)_{i\in A_l}$ such that \$0