4
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Jan 5, 2014 at 20:07
  • $\begingroup$ Nice. I wonder if bounds on $ x_i $ follow from this? $\endgroup$ Jan 5, 2014 at 21:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Jan 5, 2014 at 21:56
  • $\begingroup$ Thanks for interesting answers, feel free to turn the comments into an official answer. $\endgroup$ Jan 5, 2014 at 23:28

1 Answer 1

4
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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