Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $a_1,\cdots, a_n$ be integers such that $a_i\geq 2$ for all $i$ and $k>0$ another integer.

I am interested in whether there exist integers $x_1,\cdots, x_n$ with $0<x_i<a_i$ satisfying:

$$ \frac{x_1}{a_1}+ \cdots + \frac{x_n}{a_n}=k \ \ (*)$$

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$.

Question: For what pairs $n,k$ is there a polynomial $F$ whose inputs are $\text{lcm}$ of various subsets of $\{a_i\}_{1\leq i\leq n}$ such that (*) has a solution in the specified range if and only if $F\neq 0$ (see some examples I have in mind below)?

Some observations: If $k\geq n$ then $F\equiv 0$ works, trivially.

Some calculations for small values of $(n,k)$ suggest the following strange function: for each subset $I \subset \{1,\cdots,n\}$ define $$f_I(a_1,\cdots,a_n):= \frac{\prod_{i\in I}a_i}{\text{lcm}\{a_i\}_{i\in I}}$$

For $I=\varnothing$ we set $f_I=1$. Let:

$$F(a_1,\cdots,a_n):= \sum_{I\subset \{1,\cdots,n\}}(-1)^{|I|}f_I(a_1,\cdots,a_n) $$

(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 not 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?

PS: I am not sure what tags should be used. Please feel free to re-tag.

EDIT: Apparently this question is related to existence of lattice points on a polytope. I checked through some of the references pointed to in this question on MO, but could not find the exact answer to what I wanted.

share|improve this question
    
Could you elaborate on "probably (3,1)?" –  Douglas Zare Jan 28 '10 at 10:16
    
@Douglas: I used brute force but did not check everything carefully. –  Hailong Dao Jan 28 '10 at 11:21
    
I think I'll delete my "answer" below, since it doesn't seem to be of value to this problem. Although, I'll leave the remark that if the $x_i$ in (*) are allowed to be chosen from the set of integers. Then you can choose $x_2=x_3=\cdots=x_n=0$ and $x_1=ka_1$ to get a solution. –  Douglas S. Stones Jan 31 '10 at 5:29
add comment

1 Answer

 I don't know if you're still interested in this problem Hailong, but here is a partial result. I make two natural restrictions :
  • 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$ ).

  • 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 :

(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))$.

Note that the polynomial is independent of $k$.

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<\alpha_l < |A_l|$. Restriction 1 ensures that we may find, for each $l$ $(x_i)_{i\in A_l}$ such that $0<x_i<a_i (i\in A_l)$ and $\sum_{i\in A_l}\frac{x_i}{a_i}=\alpha_l$. So we are done.

share|improve this answer
    
Dear Ewan, I am still very interested! I kind of need a formula to work without extra conditions, but your result is very nice. Thanks and +1. –  Hailong Dao Feb 11 '10 at 1:16
    
Actually, I am now confused, (iii) seems to be equivalent to $gcd(a_i,a_j)>1$ for all pair $i\neq j$? –  Hailong Dao Feb 11 '10 at 6:31
    
You're right, I interchanged $+$ and $\times$ : $F$ is the product of the $G_i$'s, not the sum, and $G_i$ is a sum not a product. I'll correct this in my answer. The polynomial $G_i$ is always positive, and it is equal to 0 iff all the $a_ia_j-\text{lcm}(a_i,a_j)$ are zero, iff $a_i$ is prime to all the other $a_j$'s. –  Ewan Delanoy Feb 11 '10 at 9:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.