I have a question about geometry. Let $\displaystyle\mathbf 1:=\sum_{i=1}^ne_i$. Further let $w\in \mathbb R^n$ be arbitrary. For $g=\{w+t\mathbf 1 : t\in \mathbb R\}$ I would like to show that $u\in g$ and $v\in \mathbb Z^n$ exist with $\|u-v\|<\frac{1}{2\sqrt 3}\sqrt{n}$. I realize that it doesn't hold for "small" $n\in \mathbb N$, but I think it should hold for large ones.
Let me write what I have been thinking about: Since $g$ intersects the hyperplane $H=\{x\in \mathbb R^n : x_n=0\}$ w.l.o.g. we can assume that $w\in H$. Now, if we choose the point $v\in \mathbb Z^n$ that has the smallest distance in each component of $w$, we know $|v_i-w_i|\leq \frac 12$ for $1\leq i<n$ and $v_n=w_n=0$.
On the other hand, we know that the distance from $g$ to this $v$ is \begin{align*} d(g,v)=\| (v-w) - \frac 1n\langle v-w, \mathbf 1\rangle\mathbf 1 \|. \end{align*} If we set $p:=v-w$ we get \begin{align*} d(g,v)^2 &=\| p - \frac 1n\langle p, \mathbf 1\rangle\mathbf 1 \|^2\\\ &=\| p\|^2-2\frac 1n\langle p, \mathbf 1\rangle\cdot\langle p, \mathbf 1\rangle + \frac{1}{n^2}\langle p, \mathbf 1\rangle^2\cdot \| \mathbf 1\|^2\\ &=\| p\|^2-\frac 2n\langle p, \mathbf 1\rangle^2 + \frac{1}{n}\langle p, \mathbf 1\rangle^2\\ &=\| p\|^2-\frac 1n\langle p, \mathbf 1\rangle^2. \end{align*} Now the problem is, if I have, for example, $p=(\underbrace{\frac 12, \ldots, \frac 12}_{\frac{n-1}{2}\ \text{times}}, \underbrace{-\frac 12, \ldots, -\frac 12}_{\frac{n-1}{2}\ \text{times}}, 0)$, then $d(g,v)=\frac{\sqrt{n-1}}{2}$. But in this case there is a point $v'\in\mathbb Z^n$ such that $p'=(\underbrace{\frac 12, \ldots, \frac 12}_{n-1\ \text{times}}, 0)$ and then $d(g,v')=\sqrt{\frac 12-\frac{1}{4n}}\approx \frac{1}{\sqrt 2}$. The choice of my lattice point would be bad in this case, but my hypothesis is still correct.
Does anyone have an idea?
This answer gives an algorithm, not a clean answer.
We can restrict ourselves to $$w=(w_1,\dots,w_n)\in[0,1)^n,w_1\leq w_2\leq \cdots \leq w_n.\tag1$$
It is not hard to take a general $w$ and covert it to such a question for a $w$ satisfying $(1).$
You can even choose $w_1=0,$ because if $(w_1,\dots,w_n)$ satisfies $(1)$ then $(0,w_2-w_1,\cdots,w_n-w_1)$ satisfies $(1)$ and is on the same line.
We can start by finding distance to the integer point $v\in \{0,1\}^n$ nearest the line segment $w+t\mathbf 1$ with $t\in [0,1-w_{n}).$ The nearest point will be of the form: $$(0,\dots,0,1,\dots,1).$$
The nature of $w$ will restrict which $v_{i}$ can be $0.$ For example, if $w_i+(1-w_n)<\frac12,$ we know that $v_i=0.$ If $w_i>\frac12$ then $v_i=1.$
Then for $t\geq 1-w_n,$ we can switch to $w’=(0,1-w_n,1-(w_n-w_2),\dots,1-(w_n-w_{n-1}).$
We repeat and get a different $w$ for $t\in [1-w_{n-k+1},1-w_{n-k}).$ So we solved this question $n$ different times, for $k=0,1,\dots n-1$ and $w_{n+1}$ is taken to be $1.$
The answer is the minimal distance.
(It’s slightly harder if two of the $w_i$ are in equal. Then the next $w$ have to “skip” an index. If the old $w$ is $(0<w_1<w_2=w_3)$, the new $w$ is $(0,0,1-w_2,w_1+1-w_2.$)
I think finding the nearest point in $\{0,1\}^n$ given $w$ is “not hard.”
In general, the square of the distance of a point $v$ to a line $w+t\mathbf 1$ is computed by finding $t$ which minimizes $(v-w)^2-2t(v-w)\cdot \mathbf 1+ nt^2.$ This happens when $t=\frac{(v-w)\cdot \mathbf 1}{n}.$
Finding the minimum of the square of the distance is good enough, and that is this:
$$\|v-w\|^2-\frac{\left((v-w)\cdot \mathbf 1\right)^2}{n}$$
I don’t see an obvious way to use this to restrict $v$ other than the restrictions listed above.
It turns out (see below) we can skip the cases $(0,0,\dots,0)$ and $(1,1,\cdots 1).$ This is because the $t$ in those cases is always outside the range $[0,1-w_n),$ unless $w=0.$ When it is outside that range, we essentially get to re-look at the integer point in another range.
More generally, first compute $nt=(v-w)\cdot 1$ and ensure $0\leq nt<n(1-w_n).$
If $v_k$ is the vector starting with $n-k$ zeros then $k$ ones, then $nt_k=(v_k-w)\cdot \mathbf 1=k-(w_1+\cdots +w_n).$ So you need $$ \sum w_i\leq k<n(1-w_n)+\sum w_i\tag{2}$$
In particular, there are at most $\lceil n(1-w_n)\rceil$ possible $k.$
This means means more generally that for any such problem, there are at most about $2n$ cases.
Given $$D_k^2=\|v_k-w\|^2-\frac{\left((v_k-w)\cdot \mathbf 1\right)^2}{n}$$
we have $$D_k^2=\|w\|^2+k-2\sum_{i=n-k+1}^n w_i-\frac{\left(k-\sum_{i=1}^n w_i\right)^2}{n}$$
Then $$D_{k+1}^2=D_{k}^{2}+1-2w_{n-k}-\frac{2\left(k-\sum_{i=1}^{n}w_i\right)+1}{n}$$
So this lets us find $D_k^2$ recursively, pre-calculating $w\cdot w$ and $w\cdot \mathbf 1=\sum_{1}^n w_i.$ Then $D_0^2=w\cdot w-\frac{(w\cdot \mathbf 1)^2}{n},$ and then compute $D_k$ recursively.
This means we can solve the problem at minimum in $O(n^2)$ cacluatioms.
If the minimum is not at $k=0,n,$ we can we know for the minimum $k$ satisfies $D_{k}\leq D_{k-1},D_{k+1}.$ So this mean:
$$0\leq n(D_{k-1}-D_k)=2nw_{n-k+1}-n+2k-1+2w\cdot \mathbf 1$$
and
$$0\leq n(D_{k+1}-D_{k})=-2nw_{n-k}+n-2k-1-2w\cdot \mathbf 1$$
Adding these two together and rearranging, you get:
$$\frac1n\leq (w_{n-k+1}-w_{n-k})\tag3$$
That limits you to a great extent in considering which $v_k$ to consider.
For example, if we start with $w=\left(\frac{10}{3},\frac95,\frac{13}2\right)$ we can get $w’=\left(\frac13,\frac12,\frac{4}5\right).$ Then we get $w^{(0)}=\left(0,\frac16,\frac7{15}\right).$ And we have to check distances squared to points $v_1,v_2.$ But $(3)$ fails in both cases.
Then we check $w^{(1)}=\left(0,\frac7{15},\frac{7}{10}\right).$ Here we again need to check $v_1,v_2.$ But $(3)$ eliminates $v_1.$
Finally, we check $w^{(2)}=\left(0,\frac{3}{10},\frac{5}{6}\right).$ Here, we check only $v=v_1.$
If we had started with $w^{0}=(1/6,1/2,5/6)$ we’d have had to check more cases.
We can clearly remove the case $v=(0,\dots,0)$ because the distance between that point and $w+t\mathbf 1$ is strictly increasing as $t$ increases, so the point on the line closest to the point with the most zeros is minimized outside $[0,1)^n$ unless the nearest point to $(0,\dots,0)$ is exactly at $w.$
The same is true for $(1,\dots,1),$ except the function is increasing.
But then $(w-v)\cdot \mathbf 1=0,$ and the terms of $w-v$ are all $\geq 0.$ So this only possible if $w=0,$ which is easily solved.