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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < September 7 ! width="25%" align="center"|<< Aug | September | Oct >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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. $\mathrm{\forall }i\in \{1,\dots ,n\}:H\supset \prod _{j=1,\dots ,n}\{\begin{array}{cc}[p,q]& \text{if}j=i\\ [0,1]& \text{else}\end{array}$

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

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)