2
$\begingroup$

This is probably known, but I have not located a reference.

Let $P$ be the convex hull of $k$ points in $\mathbb R^n$ with rational coordinates. Consider the Euclidean square norm function $F:P\to\mathbb R$, $F(x)=||x||^2$.

Is it true that $\mathrm{min}_{x\in P}F(x)$ is rational?

$\endgroup$
5
  • $\begingroup$ Could you expand on your question? By "in $P$" do you mean "inside $P$"? (I assume so.) By squared norm of $p$, do you mean the squared Euclidean length of $p$ from the origin? And by "of a point" do you mean: over all points? $\endgroup$ Commented Dec 5, 2020 at 22:12
  • 1
    $\begingroup$ @JosephO’Rourke, I think the answers to your questions are all yes. $\endgroup$
    – user44143
    Commented Dec 6, 2020 at 1:15
  • $\begingroup$ Thanks for clarifying the question. If the origin is in $P$, then the min is zero. Otherwise, the min should be where an origin-centered sphere just touches $P$. (Which doesn't answer the question...) $\endgroup$ Commented Dec 6, 2020 at 2:15
  • $\begingroup$ @JosephO'Rourke I think that might just about answer the question? Since the sphere is tangent to $P$, the radius to the point of intersection is perpendicular to the $d$-dim face of $P$ it intersects, for some $d < n$. Since the faces of $P$ are defined over $\mathbb Q$, this means the radius has rational slope, so the intersection point is rational as well. The only case where this 'perpendicularity' isn't defined is if $d=0$ and the intersection point is a vertex, but that's already rational. $\endgroup$ Commented Jan 5, 2021 at 7:13
  • $\begingroup$ @ClaudioGorodski Does this argument look correct? $\endgroup$ Commented Jan 6, 2021 at 17:22

2 Answers 2

1
$\begingroup$

Yes, this is true in general case. Let $P={\rm conv} M$ for a finite set $M\subset \mathbb{Q}^n$, and let $x_0$ be a minimizer of $\|x\|^2$ over $x\in P$. I am going to prove that $x_0\in \mathbb{Q}^n$, that implies $\|x_0\|^2\in \mathbb{Q}$.

Consider the plane $\alpha:=\{x\colon \langle x,x_0\rangle=\|x_0\|^2\}$ passing through $x_0$ and orthogonal to $x_0$, and the half-space $\alpha_+:=\{x\colon \langle x,x_0\rangle\geqslant \|x_0\|^2\}$. Note that $P\subset \alpha_+$: otherwise, if $p\in P$ satisfy $\langle p,x_0\rangle< \|x_0\|^2$, then $$\|x_0+t(p-x_0)\|^2=\|x_0\|^2+2t\langle x_0,p-x_0\rangle+t^2\|p-x_0\|^2<\|x_0\|^2$$ if $t>0$ is small enough, that contradicts to minimality as $x_0+t(p-x_0)\in P$ for $t\in (0,1)$.

Choose the minimal number of points $v_1,\ldots,v_r\in M$ for which $x_0\in {\rm conv}(v_1,\ldots,v_r)$. Then $x_0=c_1v_1+\ldots+c_rv_r$ for strictly positive $c_i\in (0,1)$, $\sum c_i=1$. We have $v_i\in \alpha$ for all $i$, otherwise $x_0$ would lie in the interior of $\alpha_+$. Next, the vectors $v_r-v_1,v_r-v_2,\ldots,v_r-v_{r-1}$ are linearly independent. Indeed, if they were dependent, we would have a linear dependence $t_1v_1+\ldots+t_r v_r=0$ with $\sum t_i=0$. Choosing maximal $s>0$ for which all numbers $c_i+st_i$ are nonnegative (thus at least one of them equals to 0), we get a representation $x_0=\sum (c_i+st_i)v_i$, i.e., $x_0$ belongs to a convex hull of less than $r$ $v_i$'s, a contradiction. Then taking the inner product of the representation $$ x_0=v_r+\sum_{i=1}^{r-1} c_i (v_i-v_r) $$ with vectors $v_1-v_r$, $v_2-v_r$, $\ldots$, $v_{r-1}-v_r$ we get a linear system of $r-1$ equations for $c_1,\ldots,c_{r-1}$ (note that $\langle x_0, v_i-v_r\rangle=0$ as $v_i,v_r\in \alpha$, so the system does not involve $x_0$ and has rational coefficients). the matrix of this system is Gram matrix of the vectors $v_i-v_r$, $i=1,\ldots,r-1$. They are linearly independent, thus this matrix is non-singular. So, $c_i$'s may be found from this system of equations and they are rational. Thus $x_0\in \mathbb{Q}^n$.

$\endgroup$
0
$\begingroup$

I think I may have answered my own question under the assumption that the points are linearly independent as vectors in $\mathbb R^n$.

Denote the $k$ points by $v_1,\ldots, v_k\in\mathbb R^n$. Let $x=\sum_{i=1}^k x_i v_i\in P $ be the point of minimum of $F$ on $P$, so that $\sum_{i=1}^k x_i = 1$ and $x_i\geq0$ for $i=1,\ldots, k$.

By throwing away the $v_i$ with $x_i=0$, we may assume all $x_i>0$. Namely, let $I=\{i\in\{1,\ldots,k\}:x_i\neq0\}$. Then $x=\sum_{i\in I} x_iv_i$ and $\sum_{ì\in I}x_i=1$ with $x_i>0$ for all $i\in I$. Note that $x$ is the point of minimum of $F$ over $Q$, where $Q$ is the convex hull of $\{x_i\}_{i\in I}$.

Now $x$ is the point of minimum of $F$ over the affine plane $\sum_{i \in I} x_i=1$, and we can apply the Lagrange multiplier method. We want to minimize $$F((t_i)_{i\in I})=\sum_{i,j\in I}g_{ij}t_it_j,$$ where $g_{ij}=\langle v_i,v_j\rangle$, over $\sum_{i\in I}x_i=1$. The equations are $$\frac{\partial F}{\partial t_i}=2\sum_{j\in I} t_jg_{ij} =\lambda$$ and $$\sum_{i\in I}t_i=1.$$ By the assumption, the matrix $(g_{ij})$ is invertible, so we can solve the first set of equations for the $t_i$ in terms of $\lambda$, and then substitute in the last one to determine the value of $\lambda$. This shows that even the coordinates of the point of minimum are rational, so in particular, the sum of their squares.

Perhaps there is a way of reducing the general case to this one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .