From: Michael Wodzak <wodzak@lie.math.missouri.edu>
Newsgroups: sci.math
Subject: Vinogradov's Mean/Tarry Escot
Date: Thu, 21 Mar 1996 13:21:35 -0600

This problem has been with me for too long, so I'm throwing it into the
water to see who nibbles:

Consider the multigrade system of $k+1$ Diophantine equations
$$\sum_{j=1}^s x_j^i = \sum_{j=1}^s y_j^i,\ \forall i= 0,..,k.
\tag{5.1}$$
It has been known since the time of Newton that,
unless $s>k$, the $s$-tuple of $y$ values in any solution 
$(x_1 ,..,x_s,y_1,..,y_s)$ of (5.1) is necessarily a permutation of the 
$s$-tuple of $x$ values.  The (Tarry--Escot) question of whether a
non-trivial 
solution is guaranteed in the case $s=k+1$ has been  empirically
answered in the affirmative 
for $k\le 9$, but is still open for $k>9$.  The  only known solution for 
$s=k+1=10$ was
 found by L\'etac in 1942, although the distance between the smallest 
and largest integers in the solution was 47500(!).
 Of course, any such solution is completely non-trivial (C.N.T.) 
by which we will mean that
$$x_i \neq y_j,\ \forall 1\le i,j \le s.$$

A somewhat more important problem in modern Number Theory is that of
counting 
$J_{s,k}(P)$, which is the number of solutions of (5.1) such that
$$1\le x_i,y_j \le P,\ \forall 1\le i,j \le s.$$

Now, I can prove that if we define

$$ B_{v+1} =
\left(
0_1, \dots, 0_v, \binom{k+1}{0},
-\binom{k+1}{1},
\dots ,
{(-1)}^{k+1}\binom{k+1}{k+1},0,0,0,\dots
\right),
$$

$${\gamma}_m = {(-1)}^m \binom{k+1}{m-1},$$
and adopt the convention throughout the remainder that
$$\binom{m}{v}=0 \ \ \forall v\notin [0,m],$$
we have:

\smallskip
\noindent {\bf THEOREM 5.8:} Every C.N.T. solution of (5.1) corresponds
to
$$\sum_{v=1}^{\infty} z_v B_v \ \text{for some}\ \{z_v\} \in c_{00} \cap 
{\Bbb Z}^{\infty}.$$
where the number of $x$'s which take the value $n$,
$$b_n = \frac{\left| \sum_{v=1}^{\infty} z_v {\gamma}_ {(n+1)-v}\right|
+ 
\sum_{v=1}^{\infty} z_v {\gamma}_{(n+1)-v}}{2},
$$
and the corresponding number of $y$'s,
$$c_n = \frac{\left| \sum_{v=1}^{\infty} z_v {\gamma}_ {(n+1)-v}\right|
- 
\sum_{v=1}^{\infty} z_v {\gamma}_{(n+1)-v}}{2}.$$
Moreover, for each $\{z_v\} \in c_{00} \cap {\Bbb Z}^{\infty}$, the
linear 
combination $\sum_{v=1}^{\infty} z_v B_v $ gives a family of C.N.T.
solutions of
 (1) for  $2s = {\| \{ z_v B_v \} \|}_1$.

\smallskip
This is significant in that it demonstrates that $every$ solution of
(5.1) is,
in some sense, generated by the $single$ solution (and its family of 
permutations) for $P=k+2$ and $s=2^k$.  It also, $a\ fortiori$
guarantees 
 non-trivial solutions of (5.1) if $s\ge 2^k$, although we can
find a better upper bound for the minimum value of 
$s$ to guarantee such solutions.

Now we recall that a solution of (5.1) is either trivial in the sense
that the 
$s$-tuple of $y$ values is a permutation of the $s$-tuple of $x$ values,
or else
 it is non trivial in the sense that $t\in [k+1,s]$ of the $x$ values do
not 
occur as $y$ values. That is, the question of bounding $J_{s,k}(P)$ 
becomes that of bounding
$$
J_{s,k}^T(P)+J_{s,k}^U(P),
$$
where the above two addends count, respectively, the trivial and
non-trivial
 solutions as just characterised.  We have already established that
$J_{s,k}^T(P)<P^ss!$, so our remaining task is the counting of the
non-trivial
solutions.
Such a non trivial solution of (5.1) may be considered as a
C.N.T. solution of
$$\sum_{j=1}^t x_j^i = \sum_{j=1}^t y_j^i, \forall i= 1,..,k,
\tag{5.2}
$$
to which has been adjoined the same randomly picked $(s-t)$-tuple on
both the 
$x$ and $y$ sides of the equation.  Once again, the distance between
smallest
 and largest integers of such a C.N.T. solution must be at least $k+1$,
 and so the integers of any non-trivial solution must have such a
spread.  
This completely characterises the solutions of (5.1).

The question of guaranteeing a non-trivial solution of (5.1) when
$s=k+1$ now 
becomes that of finding a sequence $\{z_v\} \in c_{00} \cap {\Bbb
Z}^{\infty}$
such that ${\| \{z_v B_v \} \|}_1 = 2(k+1)$.  On the other hand, since
${\| B_v \|}_1=2^{k+1}$, for all $B_v$, one might hypothesise that, for
each
$\{z_v\} \in c_{00} \cap {\Bbb Z}^{\infty}$, the inequality
${\| \{z_v B_v \} \|}_1\ll 2^{k+1}$ is the best that can be hoped for.
That is,
even the smallest non-zero point in the lattice has $l_1$ norm  on the
order of
$2^{k+1}$, which would mean that the smallest $s$ for which a
non-trivial 
solution of (5.1) existed would have to be on the order of $2^k$.  This
is, 
however, not the case, since we have (thanks to Andrew Odlyzko):
Let $a_1,\dots a_P$ be a sequence of positive integers. If
$$F(P)=\inf \max_{|z|=1} \left|\prod_{v=1}^P (1-z^{a_k})\right| ,$$
then
$$F(P)=\exp (O (P^{\frac{1}{3}}\log^{\frac{4}{3}}P)).$$

Question:  Any thoughts as to the lattice point of smallest $l_1$ norm?
(or even $l_2$ norm for that matter)

Now, if it were the case that non-trivial solutions of 
(5.1) did not occur until $s\ge \exp (K
n^{\frac{1}{3}}\log^{\frac{4}{3}}n)$, 
then we should,  choose 
$s< \exp (K n^{\frac{1}{3}}\log^{\frac{4}{3}}n)$, so that
$J_{s,k}(P)<P^s s!$, 
and we would be done.  In reality, however,
we have no such guarantee, and so to bound
 $J_{s,k}(P)$ we cannot escape bounding
$J_{s,k}^U (P).$

Let $J_{t,k}^C(P)$ count the families of permutations of
 C.N.T. solutions of (5.2), or equivalently, the number of kernel
lattice points
 of $V_P$ with $l_1$ norm = $2t$, and let $J_{t,k}^B(P)$ count
 the number of kernel
 lattice points of $V_P$ with $l_1$ norm $\le 2t$.  We have then, 

\smallskip
\noindent
{\bf THEOREM 5.9:}
$$J_{s,k}^U(P)\ll
(s!)^2\frac{(P+s-k-2)^{P+s-k-1\frac{1}{2}}}
{(s-k-1)^{s-k-\frac{1}{2}}(P-1)^{P-\frac{1}{2}}}
J_{s,k}^B(P)
$$

And our primary task becomes that of bounding
$J_{s,k}^B(P) .$

Now, each kernel lattice point $Z$ defines a parallelepiped whose
vertices are the $2^{P-(k+1)}$ points
$$Z + \sum_{v=1}^{P-(k+1)}
{\alpha}_v B_v \ \ \text{where} \ \ {\alpha}_v = 0\ \text{or}\ 1.$$
and these parallelepipeds tessellate the kernel.

Moreover, the $P-(k+1)$ dimensional volume of each
 parallelepiped is given by

$$
\Cal V 
= 
\sqrt{\frac{({k(!!)})^2[P-k-2](!!)[P+k](!!)}{{([P-1](!!))}^2[2k+1](!!)}}
.$$

Question: Even if we know (which we do) the volume of the $l_1$ ball,
straight division does not give us the number of lattice points in the
ball because we don't know how "long and skinny" the parallepipeds are.
Any combinatorists or vector partition people out their with any ideas
as to how to count the number of lattice points in the ball?

Thanks in advance

Michal

==============================================================================

From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: hyperplanes
Date: 28 Mar 1996 08:34:55 GMT

I just noticed there is an interesting question here which has not received 
an adequate answer. I can rework the problem so that it is more precise, but
not solve it in general. For example, one case of the problem asks for the
minimum value of

  (a^2+b^2+c^2+d^2)^2 - 2(ab+bc+cd)^2 + (ac+bd)*(a^2+b^2+c^2+d^2) 
  ---------------------------------------------------------------
            3(a^2+b^2+c^2+d^2) - 4(ab+bc+cd) + (ac+bd)

in integers  a b c d  (not all zero).

In article <314DDBE7.41C6@lie.math.missouri.edu>,
Michael Wodzak  <wodzak@lie.math.missouri.edu> wrote:
>1) Given k linearly independent points in n>=k dim space, how does one
>compute the distance from the origin of the lowest dimension hyperplane
>containing those points?

Here's a non-standard answer useful for (2), below. The "hyperplane"
[I would prefer to use that term for codimension 1] is the set of points
of the form w = Sum( t_i p_i )  where  {p_1, ..., p_k}  are the points and
{t_1, ..., t_k}  are real numbers which sum to  1. The distance from the
plane to the origin is the length of the vector joining  0  to  w  when
w  is the unique point in the plane for which this vector is
perpendicular to the plane. That is, you may find this point  w  by
solving the linear equations
	Sum( t_i p_i ) . (p_j - p_1) = 0
for the variables  t_i. (These are in addition to the equation  Sum(t_i) = 1,
of course. The "." stands for the inner product.)

>2) Let a_1,...,a_k be integers, not all zero, and let n>=k. Consider the
>(n-k)+1 points 
>(a_1,...,a_k,0,0,...,0),
>(0,a_1,...a_k,0,....,0),
>...
>(0,0,...,0,a_1,...,a_k) 
>in n dim space.  These ponits are clearly linearly independent.  What
>choice of a_1,...,a_k minimises the distance of hyperplane from origin?

The best I can do is provide an explicit formula for that distance in terms
of the variables  a_1,..., a_k.

Let  s : R^n -> R^n  be the "shift" map 
	s(x_1, ..., x_n) = (0, x_1, ..., x_(n-1)).
Note that  s  is an isometry on the subspace  R^(n-1)  of  R^n, and that
more generally  s^j  is an isometry on   R^k  if  k+j <= n.

Given a fixed vector  v = (a_1, ..., a_k)  in  R^k, we seek the closest point
to the origin in the affine space spanned by  {v, s(v), ..., s^(n-k)(v) }.
As in  (1) above, this point is a sum  Sum( t_i s^i(v) )  in which
Sum( t_i ) = 1  [Note that the index set is  {0, 1, ..., n-k}  in these sums.]

The other equations characterizing these  t_i  are that
	0 = ( Sum( t_i s^i(v) ) ) . ( s^j(v) - v )
Using the fact that  s  preserves inner products on these vectors, we may
simplify these sums. Write  u(m) for the dot product  s^m(v) . v; then
the preceding equation is
	0 = Sum( t_i ( u(|j-i|) - u(i) ) )
that is,
	Sum( t_i u(|j-i|) ) = Sum( t_i u(i) )  [j = 1, 2, ... n-k]...(*)

Well, these equations seem not to admit any particularly elegant solution,
but we may proceed anyway. The distance the poster wanted to compute is
the length of this vector  Sum( t_i s^i(v) ). The square of this distance
is the inner product
	(Sum( t_i s^i(v) ) ) . ( Sum( t_j s^j(v) ) ) =
	= Sum( t_i t_j u(|i-j|) )
From  the previous paragraph, the sum over all i is the same for each j,
giving us
	Sum(t_j) * Sum(t_i u_i).
Of course, the first factor is one! So the square of the distance is the
common value of the right-hand sides of all the equations in  (*).

Thus we have an expression for the distance from this plane to the origin:
It's the square root of  Sum( t_i u(i) ), where  u(i) = Sum( a_k a_(k+i) )
and the  t_i  are selected to solve the linear equations  (*).

There are a few easy cases, for large  k  and for small  k.

If  k=n, the only equation is  t_0 = 1; the distance is then sqrt(u(0)),
the length of the one vector  v = (a_1, ..., a_n).

If  k=n-1, the equations are  t_0 + t_1 = 1  and  
u(0) t_0 + u(1) t_1 = u(1) t_0 + u(0) t_1 ; thus  t_0=t_1=(1/2)  (the closest
point is midway between the two), and the distance from the origin is
sqrt( (u(0) + u(1) )/2).

When  k=n-2, my computations show a much less clean answer: the square of
the distance to the origin is
	(u(0)^2 - 2 u(1)^2 + u(2)u(0)) / ( 3 u(0) - 4 u(1) + u(2) ).
(This is the sub-problem with which I opened this post.)

There are other simplifications if  k  is small, since  u(m)  is clearly
zero if  m >= k. So for example when  k=1  (i.e., the vector  v  and all its
shifts  s^j(v)  lies on the coordinate axes), the square of the distance
to the origin is  u(0)/(n-k+1). 

Once the expressions for the distance to the origin are obtained, one
may of course look for the minimal values for this distance among
integer points  v = (a_1, ..., a_k). I won't do so.

As far as a general pattern, I note that (from Cramer's rule) the
square of the distance from the origin will always be a homogenous
polynomial of degree (n-k)  in the  u(i), divided by another
polynomial of degree one less. Thus the poster's original question (2)
can be phrased as asking for the non-zero point  v  in a  lattice  Z^k
on which a certain positive function  Q  attains its minimum, this
Q growing quadratically   ( Q(rv) = r^2Q(v) ).

The reason I mention this is that this is roughly the setting in which
the LLL lattice-minimization algorithm was established. I'm sorry, I don't
have my resources with me right now, so I don't know what other
conditions  Q  was to satisfy in that algorithm. (Traditionally, it's
used when  Q  is a quadratic form on  Z^k, but I'm pretty sure that's
not completely necessary). Thus in principle the poster could, for any 
specific  k  and  n, possibly use LLL to determine very small (if not 
necessarily minimal) choices for the  a_i.

This poster has had an interest in the problem of multigrades, to
which the present questions are related. Others new to this circle of
problems may wish to consult some old posts in this area,
	94/multigrades
[URL updated 1999/01 -- djr]
It's notoriously easy to restate one likely-but-hard-to-prove conjecture
in this topic and produce yet another.

dave