Wikipedia:Reference desk/Archives/Mathematics/2018 September 8

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 8

Hyperrectangle contains most of the cube, but not its vertices

Let $n\in \mathbb {N}$, and let $p,q\in (0,1)$, such that $p<q$.

Is there a hyperrectangle H satisfies:

1. $\forall i\in \{1,\dots ,n\}:H\supset \prod _{j=1,\dots ,n}\left\{{\begin{matrix}[p,q]&{\text{if}}~j=i\\{}[0,1]&{\text{else}}\end{matrix}}\right.$

2. $\{0,1\}^{n}\cap H=\emptyset$

In 2D I was able to find such a hyperrectangle, but how about 3D and higher dimensions? Is there such a hyperrecangle? — Preceding unsigned comment added by 2.53.39.115 (talk) 07:45, 8 September 2018 (UTC)

First, the algebra is a bit simpler if you change the interval from [0, 1] to [-1, 1], just scale and translate accordingly. That said, I'm pretty sure that for n=3 the answer is no for any p and q. It is sufficient to show that if a rectangular cuboid H contains points (p, ±1, ±1), (±1, p, ±1), (±1, ±1, p), with -1<p<1 then H contains one of (±1, ±1, ±1). To prove this, let H be defined by

L_u ≤ u₁x+u₂y+u₃z ≤ M_u

L_v ≤ v₁x+v₂y+v₃z ≤ M_v

L_w ≤ w₁x+w₂y+w₃z ≤ M_w

where u = (u₁, u₂, u₃), v = (v₁, v₂, v₃), w = (w₁, w₂, w₃) are mutually orthogonal, non-zero vectors. Let

U = {(sign(u₁), sign(u₂), sign(u₃)), (-sign(u₁), -sign(u₂), -sign(u₃))} if all the u_i are nonzero,

and

U = ∅ otherwise.

Similarly define V and W. The sets U, V and W have at most 2 elements each, and {(±1, ±1, ±1)} has eight elements, so the difference {(±1, ±1, ±1)}\(U∪V∪W) is non-empty, say

s = (s₁, s₂, s₃)

is an element. We have s is one of the vertices of the cube, and I claim that s satisfies each of the three inequalities above. I'll prove the first inequality with the other two being similar. There are two possibilities, either some u_i=0, or there is i so s_i and u_i have the same sign, and j so that s_j and u_j have opposite signs. In the first case, take i=1, i=2 and i=3 being similar. Then u₁=0 and note that

(p, s₂, s₃) ∈ H,

so

L_u ≤ u₁p+u₂s₂+u₃s₃ ≤ M_u.

But u₁=0 so

u₁p+u₂s₂+u₃s₃ = u₁s₁+u₂s₂+u₃s₃

and

L_u ≤ u₁s₁+u₂s₂+u₃s₃ ≤ M_u.

For the second case, suppose u₁ and s₁ have the same sign, and u₂ and s₂ have opposite signs, the remaining possibilities being similar. Note that

(p, s₂, s₃) ∈ H

so

L_u ≤ u₁p+u₂s₂+u₃s₃.

Also |p| < 1 so

u₁p ≤ |u₁p| < |u₁| = u₁s₁

and therefore

L_u ≤ u₁s₁+u₂s₂+u₃s₃.

Also note that

(s₁, p, s₃) ∈ H

so

u₁s₁+u₂p+u₃s₃ ≤ M_u.

Again |p|<1 so

-u₂p ≤ |u₂p| < |u₂| = -u₂s₂

and

u₂p ≥ u₂s₂

and therefore

u₁s₁+u₂u₂+u₃s₃ ≤ M_u.

This proves both parts of the first inequality, and as noted the other inequalities are similarly true, therefore

(s₁, s₂, s₃) ∈ H.

This argument is rather fiddly and there were a couple previous versions where I discovered fatal flaws while writing them up; hopefully this version is correct. Note that I don't seem to use anywhere that u, v and w are orthogonal, so it looks like it remains true for parallelepipeds in general. The same argument works for n>3, the crucial fact needed being 2n<2ⁿ. So n=2 is actually the exceptional case. --RDBury (talk) 09:17, 9 September 2018 (UTC)

Actually there is a much more general theorem provided you apply some machinery of convex polytopes. Namely:

If P is a bounded convex polytope, Q a convex polytope which contains at least one point from every edge of P, and Q has fewer faces than P has vertices, then Q contains a vertex of P.

Proof: Suppose not. Every vertex of P is then excluded by some face of Q, in other words for each vertex v of Q there is a face of P, defined by L(x)=0 say, so that L(x)≤0 for x in Q and L(v)>0. There are more vertices of P than faces of Q, so two of the vertices must be excluded by the same face. In other words there is a linear function L so that L(x)≤0 for x in Q, and vertices v and w of P so that L(v)>0 and L(w)>0. If v and w are connected by and edge e, then L(y)>0 for all y in e, but Q contains a point of every edge of P and we have a contradiction. If L(v) is not the maximum value of L on P then apply the simplex algorithm to obtain an adjacent vertex u with L(u)>L(v)>0. This implies a contradiction as before, so L(v)=M, the maximum value of L on P. Similarly, L(w)=M. Then P∩{x: L(x)=M} is a polytope with at least two vertices, and therefore has an edge, which in fact is also an edge of P, again leading to a contradiction. There is a contradiction in every case so the initial assumption is incorrect and the theorem is true.

In the present case P is the hypercube with 2ⁿ vertices, and Q is a parallelepiped with 2n<2ⁿ faces. The simplest case is that if a triangle Q contains a point from every edge of a convex quadrilateral P, then Q must contain a vertex of P. This might be proven with just high school geometry but it would be a challenge. --RDBury (talk) 23:18, 9 September 2018 (UTC)

I like this theorem very much! Thank you! 2.53.159.234 (talk) —Preceding undated comment added 06:04, 11 September 2018 (UTC)

Notice however that a hyperrectangle (or even just a 2D-plane) that touches each face but doesn't contain any vertex does exist: After changing the interval from [0, 1] to [-1, 1] as RDBury sugggested above, in order to touch every face of the cube, you just need to take some hyperrectangele that contains the points $\{(0,1,\dots ,1),(0,-1,\dots ,-1),(1,\dots ,1,0),(-1,\dots ,-1,0)\}$. Actually, these points are linearly depndent, so you just need to to contain the points $\{(0,1,\dots ,1),(1,\dots ,1,0)\}$.

Hope this helps. עברית (talk) 17:42, 15 September 2018 (UTC)