MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For each $k\ge 1$ there is a sequence $x_{1,k},\ldots,x_{k,k}$ of positive integers such that for all nonnegative integers $ a_i $, $$ \sum_{i=1}^k a_i x_{i,k} =2\sum_{i=1}^k x_{i,k} \quad\Longrightarrow\quad a_1=\cdots= a_k=2 $$ (For $k=3$ the minimal example seems to be $(9, 12, 17)$.)

This is easy to prove by induction using only knowledge of modular arithmetic. But is there a more general theory that this result fits into?

share|cite|improve this question
It follows from the fact that there are rational points in every nonempty open subset of $\mathbb R$. Consider the set of $x_1,\dots,x_k$ such that $1<x_1<2,\dots, 1<x_k<x_2$ and $\sum_{i=1}^k a_i x_i$ does not equal $\sum_{i=1}^k 2 x_i$ for each sequence $a_1,a_k$ satisfying $\sum_{i=1}^k a_i \leq 4k$ and one of the $a_i\neq 2$. This is an open cube minus finitely many hyperplanes, hence a nonempty open set. It has a rational point. Clear denominators to get integer solutions to your equation. – Will Sawin Jan 5 '14 at 20:07
Nice. I wonder if bounds on $ x_i $ follow from this? – Bjørn Kjos-Hanssen Jan 5 '14 at 21:02
Certainly we can take $x_i<2N+4$, where $N$ is the number of hyperplanes. This is because there are $(N+1)^k$ points in the cube that are rational numbers of denominator $N+2$, and each hyperplane includes at most $(N+1)^{k-1}$ of them. so one of them must not be on any hyperplane. The number of hyperplanes is one less than the number of ways to put $4k$ balls in $k+1$ boxes, which is $\left(\begin{array}{c} 5k \\ k \end{array} \right)$. This gives a bound. By putting some effort into optimization, this can probably be improved dramatically. – Will Sawin Jan 5 '14 at 21:56
Thanks for interesting answers, feel free to turn the comments into an official answer. – Bjørn Kjos-Hanssen Jan 5 '14 at 23:28
up vote 4 down vote accepted

Many results of this type can be proven by a basic existence of rational points argument. For any finite set of nontrivial linear equations, we can find a set of integers that does not satisfy any of them. To replace the infinite set of equations in the question with a finite set, we need some kind of bound on the $a_i$, which we obtain from a bound on the $x_i$.

If $N< x_1, \dots, x_k < 2N$, then any $a_i$ satisfying the equation $\sum _{i=0}^k a_i x_i = \sum_{i=0}^k 2 x_i$ must satisfy $\sum_{i=0}^k a_i \leq 4 k$. This gives us finitely many linear equations to not satisfy. Specifically, the number of nonnegative integer solutions to $\sum_{i=0}^k a_i \leq 4k$ is $\left(\begin{array}{c} 5k \\ k \end{array}\right)$ because it is equal to the number of ways to place $4k$ balls into $k+1$ boxes.

It takes $N-1$ linear equations to cover all the integer points in the hypercube $N< x_1, \dots, x_k < 2N$, since there are $(N-1)^k$ points and each hyperplane can contain at most $(N-1)^{k-1}$. So setting $N= \left(\begin{array}{c} 5k \\ k \end{array}\right)+2$, we can find $x_1,\dots,x_k$ which have your desired property.

This bound is exponential, about $12.21^k$. One could be much more careful in finding the bound by choosing the convex region more carefully, eliminating more of the equations, using better estimates for the number of points on the hyperplanes, and so on. I'm not sure how much one could improve this bound - could one do better than exponential?

share|cite|improve this answer

Your Answer


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.