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$ Dec 5, 2020 at 22:12
  • 1
    $\begingroup$ @JosephO’Rourke, I think the answers to your questions are all yes. $\endgroup$
    – user44143
    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$ 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$ Jan 5, 2021 at 7:13
  • $\begingroup$ @ClaudioGorodski Does this argument look correct? $\endgroup$ 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$

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.